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:
'a' is 'z', and the mirror of 'b' is 'y', and so on.'0' to '9'.
'0' is '9', and the mirror of '1' is '8', and so on.For each unique character c in the string:
m be its mirror character.freq(x) denote the number of times character x appears in the string.|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.
Example 1:
Input: s = "ab1z9"
Output: 3
Explanation:
For every mirror pair:
c |
m |
freq(c) |
freq(m) |
|freq(c) - freq(m)| |
|---|---|---|---|---|
| a | z | 1 | 1 | 0 |
| b | y | 1 | 0 | 1 |
| 1 | 8 | 1 | 0 | 1 |
| 9 | 0 | 1 | 0 | 1 |
Thus, the answer is 0 + 1 + 1 + 1 = 3.
Example 2:
Input: s = "4m7n"
Output: 2
Explanation:
c |
m |
freq(c) |
freq(m) |
|freq(c) - freq(m)| |
|---|---|---|---|---|
| 4 | 5 | 1 | 0 | 1 |
| m | n | 1 | 1 | 0 |
| 7 | 2 | 1 | 0 | 1 |
Thus, the answer is 1 + 0 + 1 = 2.
Example 3:
Input: s = "byby"
Output: 0
Explanation:
c |
m |
freq(c) |
freq(m) |
|freq(c) - freq(m)| |
|---|---|---|---|---|
| b | y | 2 | 2 | 0 |
Thus, the answer is 0.
Constraints:
1 <= s.length <= 5 * 105s consists only of lowercase English letters and digits.Problem Overview: You are given a string and must measure the mirror frequency distance between characters and their alphabet mirrors. In the English alphabet, mirrors are pairs like a ↔ z, b ↔ y, c ↔ x. The task reduces to counting how often each character appears and comparing those counts with its mirrored partner.
Approach 1: Recount Frequencies for Each Mirror Pair (Brute Force) (O(26 * n) time, O(1) space)
For every mirror pair such as ('a','z'), scan the entire string and count how many times each character appears. Compute the distance between their counts and accumulate the result. This repeats a full pass of the string for each pair, leading to roughly 26 * n operations. The approach is straightforward but inefficient because the same characters are counted many times.
Approach 2: Hash Table Frequency Counting (O(n) time, O(k) space)
First iterate through the string once and store character frequencies in a hash table. Then iterate over the 13 mirror pairs of the alphabet. For each character c, compute its mirror using 'z' - (c - 'a') and look up both counts in the map. The mirror frequency distance is derived directly from these two values. This avoids repeated scans and reduces the total work to one pass plus constant-time lookups.
Approach 3: Fixed Array Counting (Optimal) (O(n) time, O(1) space)
A hash table works, but the alphabet size is fixed. Use an integer array of size 26 to count occurrences. Traverse the string once and increment freq[c - 'a']. After counting, use a two-pointer style sweep from both ends of the array (i = 0, j = 25) and compare frequencies of mirrored characters. Each step processes one mirror pair. This technique leverages constant alphabet size and replaces hash lookups with direct indexing, making it faster in practice. The method relies on simple string iteration and counting logic.
Recommended for interviews: Start by mentioning the brute-force idea to show you understand the mirror-pair relationship. Then move quickly to the frequency-count approach. Interviewers typically expect the O(n) counting solution using a 26-length array or hash map because it demonstrates efficient use of frequency tables and constant-time lookups.
Solutions for this problem are being prepared.
Try solving it yourself| Approach | Time | Space | When to Use |
|---|---|---|---|
| Repeated Scan for Each Mirror Pair | O(26 * n) | O(1) | Useful for understanding the mirror relationship but inefficient for large strings |
| Hash Table Frequency Counting | O(n) | O(k) | General solution when characters may extend beyond a fixed alphabet |
| 26-Length Array Counting | O(n) | O(1) | Best for lowercase English strings; fastest and simplest implementation |
Practice Mirror Frequency Distance with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor