Letters and equal pairs
Preserve multiplicity in a small alphabet and count pairs as they arrive.
Anagrams need counts, not a set
For lowercase ASCII English letters, c − 'a' maps the alphabet to IDs 0 through 25. Two words are anagrams exactly when all letter multiplicities match. The words aabb and abbb have the same distinct-letter set but different counts.
Build two count arrays and compare them, or add the first word’s letters and subtract the second word’s letters into one signed balance table. Every entry must finish at zero. This 26-letter representation is specific to the stated ASCII alphabet, not general Unicode text.
Count a pair at its later endpoint
We want pairs of different positions (i, j) with i < j and equal values. When x arrives, every earlier x creates one new pair. Add freq[x] to the answer before incrementing freq[x]. Each pair is counted once, when its later position arrives.
Equivalently, f occurrences contribute f(f − 1)/2 pairs. For 200000 identical values, the answer is 19999900000, so use long long and widen multiplication before it happens. The streaming solution avoids a nested scan and uses O(n + U + 1) time.
// Complete C++23 program. Input: n upper, n values in [0,upper].
#include <iostream>
#include <vector>
int main() {
int n, upper;
std::cin >> n >> upper;
std::vector<long long> freq(upper + 1, 0);
long long pairs = 0;
for (int i = 0; i < n; ++i) {
int x;
std::cin >> x;
pairs += freq[x];
++freq[x];
}
std::cout << pairs << '\n';
}Know what each counter measures
A letter balance may be negative during anagram checking, so an unsigned counter is unsuitable. A frequency count is nonnegative; the pair answer can be much larger than any one frequency. Choose types for each meaning.
For anagrams with word lengths n and m, the count table uses constant extra space for this fixed alphabet, while stored input strings still occupy O(n + m). Always distinguish auxiliary table space from total explicit storage.
Frequency array
The value becomes an index. Each arrival increases freq[value] by one. This domain has ten possible values.
Input values
freq[value] — indices are values
The frequencies add up to 6, the number of input values.
Guided simulation · Change the inputs to test your understanding.
Four copies of one value arrive. How many new equal pairs does each create?
Turn the idea into code
Count equal pairs in [3, 0, 3, 5, 3, 0]. Then decide whether aabcc and cbaca are anagrams.
Give me a hint
For each value, either count earlier matches or use f(f − 1)/2. For words, compare all 26 counts.
Show the explained solution
Value 3 occurs three times and contributes 3 pairs; value 0 occurs twice and contributes 1. Total: 4. The words are anagrams: both have two as, one b, and two cs.
Your notes
Mark complete when you can explain it yourself.