3889. Mirror Frequency Distance

MediumHash TableStringCounting

LeetCode ↗

Problem Pattern Idea Example Code Complex Pitfalls

Problem Description

You are given a string s consisting of lowercase English letters and digits.

For each character, its mirror character is defined by reversing the order of its character set:

For letters, the mirror of a character is the letter at the same position from the end of the alphabet.
- For example, the mirror of 'a' is 'z', the mirror of 'b' is 'y', and so on.
For digits, the mirror of a character is the digit at the same position from the end of the range '0' to '9'.
- For example, the mirror of '0' is '9', the mirror of '1' is '8', and so on.

For each unique character c in the string:

Let m be its mirror character.
Let freq(x) denote the number of times character x appears in the string.
Compute the absolute difference between their frequencies, defined as |freq(c) - freq(m)|.

The mirror pairs (c, m) and (m, c) are the same and must be counted only once.

Return an integer denoting the total sum of these values over all such distinct mirror pairs.

Quick Interview Experience

Help others by sharing your interview experience

Have you seen this problem before?

How We Pick the Algorithm

Why Hash Table / Counting?

This problem maps to Hash Table / Counting through a short path in the full flowchart.

The core operation is counting character frequencies with a hash table and computing absolute differences between mirror character pairs.

Open in Flowchart

Intuition

The core observation is that the answer depends only on how many times each character appears in the string. So the first natural step is to count the frequency of every character using a hash table.

Once we know all the frequencies, the problem reduces to pairing each character c with its mirror character m and summing up |freq(c) - freq(m)|. The tricky part is that each pair (c, m) is the same as (m, c), so we must make sure we don't add the same difference twice.

To handle this, we walk through each distinct character c, compute its mirror m, and add the absolute difference of their frequencies. To avoid double counting, we keep track of characters we have already processed in a hash set. When we reach a character whose mirror has already been visited, we simply skip it, since that pair's contribution was already accounted for.

Computing the mirror is straightforward arithmetic:

For a letter, its mirror is chr(ord('a') + 25 - (ord(c) - ord('a'))), which maps a to z, b to y, and so on.
For a digit, its mirror is 9 - int(c), which maps 0 to 9, 1 to 8, and so on.

By combining frequency counting with a visited set to enforce the "count each pair once" rule, we naturally arrive at a clean and efficient solution.

Solution Approach

Solution 1: Hash Table

We first use a hash table freq to count the frequency of each character in string s. In Python, this is done conveniently with Counter(s).

Next, we prepare a hash set vis to keep track of characters we have already processed, and a variable ans initialized to 0 to accumulate the result.

Then, we iterate over each key-value pair (c, v) in freq, where c is the character and v is the number of times c appears in the string. For each character c, we compute its mirror character m:

If c is a letter, then m = chr(ord('a') + 25 - (ord(c) - ord('a'))), mapping a to z, b to y, and so on.
If c is a digit, then m = str(9 - int(c)), mapping 0 to 9, 1 to 8, and so on.

To avoid counting the same mirror pair twice, we check whether m is already in vis. If it is, we skip the current character with continue. Otherwise, we add c to vis and accumulate abs(v - freq[m]) into ans. Note that freq[m] is 0 when m does not appear in the string, which is handled automatically by Counter.

Finally, we return ans as the total sum of absolute differences over all distinct mirror pairs.

The time complexity is O(n), where n is the length of the string s, since we scan the string once to build the frequency table and then iterate over at most a constant number of distinct characters (26 letters plus 10 digits). The space complexity is O(|\Sigma|), where |\Sigma| is the size of the character set.

Example Walkthrough

Let's trace through the solution with a small example string:

s = "abyz1"

Step 1: Count frequencies.

We build the frequency table using Counter(s):

freq = {'a': 1, 'b': 1, 'y': 1, 'z': 1, '1': 1}

We also initialize an empty visited set vis = {} and ans = 0.

Step 2: Iterate over each distinct character and compute its mirror.

Recall the mirror rules:

Letter mirror: m = chr(ord('a') + 25 - (ord(c) - ord('a'))) → maps a↔z, b↔y, etc.
Digit mirror: m = str(9 - int(c)) → maps 0↔9, 1↔8, etc.

`c`	mirror `m`	`m` in `vis`?	Action	`freq[c]`	`freq[m]`	`\|freq[c]-freq[m]\|`	`ans`	`vis` after
`'a'`	`'z'`	No	process	1	1	`\|1-1\| = 0`	0	`{a}`
`'b'`	`'y'`	No	process	1	1	`\|1-1\| = 0`	0	`{a, b}`
`'y'`	`'b'`	Yes	skip (pair already counted)	—	—	—	0	`{a, b}`
`'z'`	`'a'`	Yes	skip (pair already counted)	—	—	—	0	`{a, b}`
`'1'`	`'8'`	No	process	1	0	`\|1-0\| = 1`	1	`{a, b, 1}`

Step 3: Walk through the key moments.

For 'a', the mirror is 'z'. Since 'z' hasn't been visited, we add |freq['a'] - freq['z']| = |1 - 1| = 0 and mark 'a' as visited.
For 'b', the mirror is 'y'. Same situation: we add |1 - 1| = 0 and mark 'b' as visited.
When we reach 'y', its mirror is 'b', which is already in vis. This pair (b, y) was already counted, so we skip it. This is exactly how double counting is prevented.
Similarly, 'z' maps to 'a', which is already visited, so we skip it too.
For '1', the mirror is '8'. Since '8' never appears in the string, freq['8'] = 0 (handled automatically by Counter). We add |1 - 0| = 1.

Step 4: Return the result.

ans = 0 + 0 + 1 = 1

The final answer is 1, contributed entirely by the unmatched digit '1' whose mirror '8' is absent from the string. The fully matched letter pairs (a, z) and (b, y) each contributed 0 because both characters appear with equal frequency.

Solution Implementation

1from collections import Counter
2
3
4class Solution:
5    def mirrorFrequency(self, s: str) -> int:
6        # Count the frequency of each character in the string
7        freq = Counter(s)
8        ans = 0
9        # Track characters that have already been processed
10        visited = set()
11
12        for char, count in freq.items():
13            # Compute the "mirror" of the current character:
14            #  - letters mirror within the alphabet: 'a' <-> 'z', 'b' <-> 'y', ...
15            #  - digits mirror within numbers:        '0' <-> '9', '1' <-> '8', ...
16            if char.isalpha():
17                mirror = chr(ord("a") + 25 - (ord(char) - ord("a")))
18            else:
19                mirror = str(9 - int(char))
20
21            # Skip if the mirror has already been visited to avoid
22            # processing the same pair twice
23            if mirror in visited:
24                continue
25
26            # Mark the current character as visited
27            visited.add(char)
28
29            # Add the absolute difference in frequency between the
30            # character and its mirror
31            ans += abs(count - freq[mirror])
32
33        return ans
34```
35
36**Additional perspective on the visited-set inconsistency:**
37
38The original logic has an asymmetry: it checks `if mirror in visited` but stores `visited.add(char)`. This means the "skip" condition only triggers when a character's mirror was previously seen. For most inputs this works because pairs are mutually mirrored (`mirror(mirror(c)) == c`), so adding `char` and later checking its `mirror` correctly catches the pair.
39
40If you want it to be unambiguous, you could store the mirror instead:
41
42```python3
43from collections import Counter
44
45
46class Solution:
47    def mirrorFrequency(self, s: str) -> int:
48        freq = Counter(s)
49        ans = 0
50        visited = set()
51
52        for char, count in freq.items():
53            if char.isalpha():
54                mirror = chr(ord("a") + 25 - (ord(char) - ord("a")))
55            else:
56                mirror = str(9 - int(char))
57
58            # Skip the pair if it was already counted from the other side
59            if char in visited or mirror in visited:
60                continue
61
62            # Record both members of the pair as visited
63            visited.add(char)
64            visited.add(mirror)
65
66            ans += abs(count - freq[mirror])
67
68        return ans
69

1class Solution {
2    public int mirrorFrequency(String s) {
3        // Count the frequency of each character in the string
4        Map<Character, Integer> frequency = new HashMap<>();
5        for (char ch : s.toCharArray()) {
6            frequency.merge(ch, 1, Integer::sum);
7        }
8
9        int answer = 0;
10        // Track characters whose mirror pair has already been processed
11        Set<Character> visited = new HashSet<>();
12
13        for (Map.Entry<Character, Integer> entry : frequency.entrySet()) {
14            char ch = entry.getKey();
15            int count = entry.getValue();
16
17            // Compute the mirror character:
18            // letters mirror within 'a'-'z' (a <-> z, b <-> y, ...)
19            // digits mirror within '0'-'9' (0 <-> 9, 1 <-> 8, ...)
20            char mirror;
21            if (Character.isLetter(ch)) {
22                mirror = (char) ('a' + 25 - (ch - 'a'));
23            } else {
24                mirror = (char) ('0' + (9 - (ch - '0')));
25            }
26
27            // Skip if the mirror character was already processed to avoid double counting
28            if (visited.contains(mirror)) {
29                continue;
30            }
31            visited.add(ch);
32
33            // Accumulate the absolute difference between the two frequencies
34            int mirrorCount = frequency.getOrDefault(mirror, 0);
35            answer += Math.abs(count - mirrorCount);
36        }
37
38        return answer;
39    }
40}
41

1class Solution {
2public:
3    int mirrorFrequency(string s) {
4        // Count the frequency of each character in the string.
5        unordered_map<char, int> freq;
6        for (char ch : s) {
7            ++freq[ch];
8        }
9
10        int ans = 0;
11        // Track characters whose pair has already been processed.
12        unordered_set<char> visited;
13
14        for (const auto& [ch, count] : freq) {
15            // Compute the mirror character:
16            //   letters: 'a' <-> 'z', 'b' <-> 'y', ...
17            //   digits : '0' <-> '9', '1' <-> '8', ...
18            char mirror;
19            if (isalpha(static_cast<unsigned char>(ch))) {
20                mirror = 'a' + 25 - (ch - 'a');
21            } else {
22                mirror = '0' + (9 - (ch - '0'));
23            }
24
25            // If this character's mirror was already handled, skip to
26            // avoid counting the same pair twice.
27            if (visited.count(mirror)) {
28                continue;
29            }
30            // Mark the current character as processed so that when we later
31            // reach its mirror, the pair is recognized as already counted.
32            visited.insert(ch);
33
34            // Look up the mirror's frequency (0 if it does not appear).
35            int mirrorCount = freq.count(mirror) ? freq[mirror] : 0;
36
37            // Add the absolute difference between the two frequencies.
38            ans += abs(count - mirrorCount);
39        }
40
41        return ans;
42    }
43};
44

1/**
2 * Calculates the sum of absolute frequency differences between each
3 * character and its "mirror" counterpart within the string.
4 *
5 * Mirror rules:
6 *   - Lowercase letters mirror around the alphabet (a<->z, b<->y, ...).
7 *   - Digits mirror around 9 (0<->9, 1<->8, ...).
8 *
9 * @param s - The input string to process.
10 * @returns The accumulated absolute difference of frequencies.
11 */
12function mirrorFrequency(s: string): number {
13    // Map each character to how many times it appears in the string.
14    const frequency = new Map<string, number>();
15    for (const char of s) {
16        frequency.set(char, (frequency.get(char) || 0) + 1);
17    }
18
19    // Helpful base char codes computed once for clarity.
20    const charCodeA = 'a'.charCodeAt(0);
21
22    let answer = 0;
23
24    // Track characters already processed to avoid double-counting pairs.
25    const visited = new Set<string>();
26
27    for (const [char, count] of frequency.entries()) {
28        let mirror: string;
29
30        if (/[a-z]/.test(char)) {
31            // Reflect a lowercase letter around the alphabet: a<->z, b<->y, ...
32            mirror = String.fromCharCode(charCodeA + 25 - (char.charCodeAt(0) - charCodeA));
33        } else {
34            // Reflect a digit around 9: 0<->9, 1<->8, ...
35            mirror = String(9 - Number(char));
36        }
37
38        // If the mirror was already encountered, skip to avoid recounting.
39        if (visited.has(mirror)) {
40            continue;
41        }
42
43        // Mark the current character as visited.
44        visited.add(char);
45
46        // Look up the mirror's frequency (0 if absent) and add the difference.
47        const mirrorCount = frequency.get(mirror) || 0;
48        answer += Math.abs(count - mirrorCount);
49    }
50
51    return answer;
52}
53

Time and Space Complexity

Time Complexity: O(n), where n is the length of the string s. Building the Counter from s requires traversing all characters in the string, which takes O(n) time. The subsequent loop iterates over the distinct characters in the frequency map (at most |Σ| entries), and each iteration performs constant-time operations such as computing the mirror character m, checking membership in vis, and updating ans. Since |Σ| ≤ n, the overall time complexity is dominated by the O(n) traversal.
Space Complexity: O(|Σ|), where Σ is the set of distinct characters in the string s. The freq counter stores at most |Σ| key-value pairs, and the vis set holds at most |Σ| characters. Thus, the additional space used is proportional to the number of distinct characters.

Pattern Learn more about how to find time and space complexity quickly.

Common Pitfalls

Pitfall 1: Forgetting to Handle Self-Mirroring Characters

A subtle but critical edge case arises when a character is its own mirror. Looking at the mirror definitions:

For digits, the range '0' to '9' has 10 elements (even count), so every digit pairs with a distinct partner ('0'<->'9', '4'<->'5', etc.). No digit mirrors to itself.
For letters, the alphabet has 26 elements (even count), so every letter also pairs with a distinct partner ('a'<->'z', 'm'<->'n', etc.). No letter mirrors to itself either.

So with the current mapping, mirror(c) != c is always true. But the danger appears if you adapt this code to a different character set with an odd size (for example, the letters 'a' to 'e', where 'c' would be its own mirror). In that case:

if char in visited or mirror in visited:
    continue
visited.add(char)
visited.add(mirror)
ans += abs(count - freq[mirror])  # adds abs(count - count) = 0, which is fine

The arithmetic accidentally yields 0 for a self-mirror, so the result happens to stay correct, but the logic is fragile. If you ever change abs(count - freq[mirror]) to something like count + freq[mirror], a self-mirror would be double-counted within the same iteration.

Solution: Explicitly guard against the self-mirror case to make intent clear and robust:

if char == mirror:
    # A character that mirrors to itself contributes |freq(c) - freq(c)| = 0
    continue

Pitfall 2: The Asymmetric Visited Check (Original Code)

In the first version, the code does:

if mirror in visited:   # checks the mirror
    continue
visited.add(char)       # but stores the character

This relies on the implicit invariant mirror(mirror(c)) == c. It works only because the mapping is a perfect involution. The flaw is that it's non-obvious and easy to break:

If the iteration order causes both c and m to be checked before either is added (impossible here since they're processed one at a time, but possible in concurrent or batched variants), you could double count.
A maintainer reading add(char) then check mirror may not realize the dependency on the involution property.

Solution: Use the symmetric version that checks and stores both members of the pair (shown in the "Additional perspective" section):

if char in visited or mirror in visited:
    continue
visited.add(char)
visited.add(mirror)
ans += abs(count - freq[mirror])

Pitfall 3: Treating Absent Mirrors Incorrectly

When the mirror character m does not appear in the string, its frequency should be 0. A common mistake is to use a plain dict and access freq[mirror] directly, raising a KeyError:

freq = dict(...)        # plain dict
ans += abs(count - freq[mirror])   # KeyError if mirror absent!

Solution: Rely on Counter, which returns 0 for missing keys instead of raising:

freq = Counter(s)
ans += abs(count - freq[mirror])   # freq[mirror] is 0 if absent — safe

If you must use a plain dict, use freq.get(mirror, 0) instead.

Pitfall 4: Misclassifying Characters

The branch if char.isalpha(): ... else: ... assumes every non-alphabetic character is a digit. The problem guarantees only lowercase letters and digits, so this is safe for valid input. However, if the input ever contains uppercase letters or symbols, str(9 - int(char)) will throw a ValueError.

Solution: Be explicit about the digit branch for defensive correctness:

if char.isalpha():
    mirror = chr(ord("a") + ord("z") - ord(char))
elif char.isdigit():
    mirror = str(9 - int(char))
else:
    continue  # ignore unexpected characters, or raise based on requirements

Note also the simplification ord("a") + ord("z") - ord(char) avoids the magic number 25 and reads more clearly as "reflect around the alphabet."

Ready to land your dream job?

Unlock your dream job with a 5-minute quiz for a personalized study roadmap!

Get My Roadmap

Discover Your Strengths and Weaknesses: Take Our 5-Minute Quiz to Get a Personalized Study Roadmap: