LeetCode Problem 3889

Difficulty: 🟡 Medium
Topics: Hash Table, String, Counting

Solution

LeetCode 3889 - Mirror Frequency Distance

Problem Understanding

We are given a string s containing only lowercase English letters (a-z) and digits (0-9).

Each character has a corresponding mirror character:

• Letters are mirrored across the alphabet.

• a ↔ z

• b ↔ y

• c ↔ x

• and so on.

• Digits are mirrored across the digit range.

• 0 ↔ 9

• 1 ↔ 8

• 2 ↔ 7

• and so on.

For every unique character c that appears in the string, we consider its mirror character m. We compute:

$$|freq(c) - freq(m)|$$

where freq(x) is the number of occurrences of character x in the string.

A crucial detail is that mirror pairs must be counted only once. If we process (b, y), we must not later process (y, b) again.

The goal is to return the sum of these absolute frequency differences across all distinct mirror pairs that are relevant to the characters appearing in the string.

The string length can be as large as 5 * 10^5, which means any solution that repeatedly scans the string or performs expensive operations per character occurrence will be too slow. We need an algorithm that runs in linear time or close to it.

An important observation is that the character universe is extremely small:

• 26 lowercase letters
• 10 digits

Only 36 possible characters exist.

This means frequency counting is very cheap, and once frequencies are known, processing mirror pairs is straightforward.

Important edge cases include:

• A character whose mirror never appears in the string.

• A mirror pair where both characters occur equally often.

• Characters that are their own mirror.

• No such character exists among lowercase letters or digits because both sets have even sizes.

• Strings consisting of only one repeated character.

• Very large strings where efficiency matters.

Approaches

Brute Force

A straightforward approach is to examine every unique character in the string and repeatedly count the occurrences of both the character and its mirror by scanning the entire string.

For each unique character:

1. Find its mirror.
2. Count occurrences of the character.
3. Count occurrences of its mirror.
4. Add the absolute difference.
5. Use a mechanism to avoid double counting.

This approach is correct because it directly implements the definition of the problem. However, counting frequencies by rescanning the string for every character is inefficient.

If there are k unique characters, each frequency computation may require O(n) work, leading to O(kn) complexity. Although k ≤ 36, this still performs unnecessary repeated scans.

Optimal Approach

The key observation is that all frequency information can be computed in a single pass.

First, build a frequency table for every character appearing in the string.

Then iterate through the unique characters. For each character:

1. Compute its mirror.
2. Form the mirror pair.
3. Process the pair only once.
4. Add the absolute frequency difference.

Because each character frequency is already known, every lookup becomes O(1).

The entire problem reduces to:

• One pass to count frequencies.
• One pass over the unique characters.

This yields linear time complexity.

Approach Comparison

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(kn)	O(k)	Repeatedly rescans the string to count frequencies
Optimal	O(n)	O(k)	Single frequency table, each mirror pair processed once

Here, k is the number of distinct characters, and k ≤ 36.

Algorithm Walkthrough

1. Create a hash map called frequency.

Traverse the string once and count how many times each character appears. This gives constant-time access to any frequency we need later. 2. Create an empty set called processed.

This set will store characters that already belong to a mirror pair that has been counted. 3. Iterate through every unique character in the frequency map.

Each unique character represents a potential mirror pair. 4. Compute the mirror character.

For letters:

• Mirror of 'a' is 'z'
• Mirror of 'b' is 'y'

This can be computed using ASCII arithmetic:

mirror = chr(ord('a') + ord('z') - ord(c))

For digits:

mirror = chr(ord('0') + ord('9') - ord(c))

5. Skip already processed pairs.

If the current character is already in processed, its mirror pair has already been counted. 6. Compute the contribution.

Retrieve:

• frequency[c]
• frequency.get(mirror, 0)

Then add:

abs(frequency[c] - frequency.get(mirror, 0))

to the answer. 7. Mark both characters as processed.

Add both c and mirror to the set so that the reverse pair will not be counted later. 8. Return the accumulated answer.

Why it works

Every mirror pair is processed exactly once because both members of the pair are added to processed after their contribution is computed. The frequency table provides the exact occurrence count for every character. Therefore, for each distinct mirror pair, the algorithm adds precisely the required value:

$$|freq(c) - freq(m)|$$

and no pair is counted twice. Since all distinct pairs are covered, the final sum is correct.

Python Solution

from collections import Counter

class Solution:
    def mirrorFrequency(self, s: str) -> int:
        frequency = Counter(s)
        processed = set()
        answer = 0

        for ch in frequency:
            if ch in processed:
                continue

            if 'a' <= ch <= 'z':
                mirror = chr(ord('a') + ord('z') - ord(ch))
            else:
                mirror = chr(ord('0') + ord('9') - ord(ch))

            answer += abs(
                frequency[ch] - frequency.get(mirror, 0)
            )

            processed.add(ch)
            processed.add(mirror)

        return answer

The implementation begins by constructing a frequency table using Counter. This allows constant-time access to the occurrence count of any character.

The processed set ensures that mirror pairs are counted only once. When a character and its mirror are processed, both are inserted into the set.

For each unique character, the mirror is computed using ASCII arithmetic. The formula works because mirror characters are positioned symmetrically within their respective ranges.

The frequency difference is then calculated using the stored counts. If the mirror character never appears in the string, frequency.get(mirror, 0) correctly returns zero.

Finally, the accumulated answer is returned.

Go Solution

func mirrorFrequency(s string) int {
	frequency := make(map[byte]int)

	for i := 0; i < len(s); i++ {
		frequency[s[i]]++
	}

	processed := make(map[byte]bool)
	answer := 0

	for ch := range frequency {
		if processed[ch] {
			continue
		}

		var mirror byte

		if ch >= 'a' && ch <= 'z' {
			mirror = byte('a' + 'z' - ch)
		} else {
			mirror = byte('0' + '9' - ch)
		}

		answer += abs(frequency[ch] - frequency[mirror])

		processed[ch] = true
		processed[mirror] = true
	}

	return answer
}

func abs(x int) int {
	if x < 0 {
		return -x
	}
	return x
}

The Go implementation follows the same algorithm as the Python version. A map[byte]int stores character frequencies, and a map[byte]bool tracks processed mirror pairs.

One convenient Go behavior is that accessing a missing key in a map of integers returns the zero value, which is exactly what we need when the mirror character does not appear in the string.

Since the maximum answer is bounded by the string length, standard Go int is sufficient.

Worked Examples

Example 1

Input

s = "ab1z9"

Frequency Table

Character	Frequency
a	1
b	1
1	1
z	1
9	1

Processing

Character	Mirror	freq(c)	freq(m)	Contribution
a	z	1	1	0
b	y	1	0	1
1	8	1	0	1
9	0	1	0	1

Total:

0 + 1 + 1 + 1 = 3

Answer:

3

Example 2

Input

s = "4m7n"

Frequency Table

Character	Frequency
4	1
m	1
7	1
n	1

Processing

Character	Mirror	freq(c)	freq(m)	Contribution
4	5	1	0	1
m	n	1	1	0
7	2	1	0	1

Total:

1 + 0 + 1 = 2

Answer:

2

Example 3

Input

s = "byby"

Frequency Table

Character	Frequency
b	2
y	2

Processing

Character	Mirror	freq(c)	freq(m)	Contribution
b	y	2	2	0

Total:

0

Answer:

0

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n)	One pass to build frequencies, then one pass over unique characters
Space	O(k)	Stores frequencies and processed characters

Since there are only 36 possible valid characters, k is bounded by 36. Therefore, the additional memory usage is effectively constant in practice. The dominant cost is the single scan of the input string.

Test Cases

sol = Solution()

assert sol.mirrorFrequency("ab1z9") == 3  # example 1
assert sol.mirrorFrequency("4m7n") == 2  # example 2
assert sol.mirrorFrequency("byby") == 0  # example 3

assert sol.mirrorFrequency("a") == 1  # mirror z absent
assert sol.mirrorFrequency("z") == 1  # mirror a absent
assert sol.mirrorFrequency("0") == 1  # mirror 9 absent
assert sol.mirrorFrequency("9") == 1  # mirror 0 absent

assert sol.mirrorFrequency("az") == 0  # balanced mirror pair
assert sol.mirrorFrequency("09") == 0  # balanced digit pair

assert sol.mirrorFrequency("aaa") == 3  # mirror absent, frequency 3
assert sol.mirrorFrequency("aaaz") == 2  # frequencies 3 and 1

assert sol.mirrorFrequency("bbbbyy") == 2  # frequencies 4 and 2
assert sol.mirrorFrequency("111188") == 0  # frequencies match

assert sol.mirrorFrequency("abcdefghijklmnopqrstuvwxyz") == 0  # all letters once
assert sol.mirrorFrequency("0123456789") == 0  # all digits once

assert sol.mirrorFrequency("a0") == 2  # two independent missing mirrors

assert sol.mirrorFrequency("aaaaaz") == 4  # large imbalance

Test Summary

Test	Why
"ab1z9"	Official example 1
"4m7n"	Official example 2
"byby"	Official example 3
"a"	Single letter
"z"	Opposite single letter
"0"	Single digit
"9"	Opposite single digit
"az"	Balanced letter mirror pair
"09"	Balanced digit mirror pair
"aaa"	Missing mirror with high frequency
"aaaz"	Unequal frequencies
"bbbbyy"	Nonzero difference within a mirror pair
"111188"	Equal digit frequencies
"abcdefghijklmnopqrstuvwxyz"	Every letter appears once
"0123456789"	Every digit appears once
"a0"	Independent letter and digit pairs
"aaaaaz"	Large frequency imbalance

Edge Cases

Character Appears but Its Mirror Does Not

Consider s = "aaa".

A common mistake is assuming every mirror character must exist in the frequency table. Here, z never appears. The implementation uses frequency.get(mirror, 0) in Python and relies on Go's zero-value map lookup behavior, correctly treating the missing mirror frequency as zero. The contribution becomes |3 - 0| = 3.

Both Members of a Mirror Pair Appear

Consider s = "byby".

A naive implementation might process b and later process y, double counting the same mirror pair. The processed set prevents this. Once (b, y) is handled, both characters are marked, so the reverse pair is skipped.

Multiple Independent Mirror Pairs

Consider s = "a0".

The letter pair (a, z) and digit pair (0, 9) are completely independent. The algorithm handles them separately because each character computes its mirror within its own character set. The result is:

• |1 - 0| = 1
• |1 - 0| = 1

Total = 2.

Large Input Size

The string may contain up to 500,000 characters. Any approach that repeatedly scans the string for frequencies would waste work. The frequency-table approach counts every character exactly once and then performs only constant-sized post-processing, ensuring efficient performance even at the maximum input size.