Skip to main content
Talentd

Mirror Frequency Distance - Solution & Explanation

MediumHash TableStringCounting9 min read
Practice this problem

Problem Statement

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', and 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', and 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.

 

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 * 105
  • s consists only of lowercase English letters and digits.

Approach Overview

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.

Solution

We first use a hash table freq to count the frequency of each character in string s.

Then, we iterate over each key-value pair (c, v) in freq, where c is the character and v is the number of times character c appears in string s. For each character c, we compute its mirror character m and calculate |freq(c) - freq(m)|. To avoid counting mirror pairs twice, we use a hash set vis to track already-visited characters.

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

The time complexity is O(n), where n is the length of string s. The space complexity is O(|\Sigma|), where \Sigma is the set of distinct characters in string s.

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Repeated Scan for Each Mirror PairO(26 * n)O(1)Useful for understanding the mirror relationship but inefficient for large strings
Hash Table Frequency CountingO(n)O(k)General solution when characters may extend beyond a fixed alphabet
26-Length Array CountingO(n)O(1)Best for lowercase English strings; fastest and simplest implementation

Video Solution

Mirror Frequency Distance|Leetcode 3889|Leetcode contest 496|weekly contest 496| weekly contest • Code Thoughts • 140 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Mirror Frequency Distance easy or hard?
Mirror Frequency Distance is generally classified as a medium difficulty problem. The challenge is recognizing that repeated counting is unnecessary and that a single frequency table allows direct comparison of mirrored characters.
Mirror Frequency Distance Python/Java solution
Most implementations follow the same pattern: build a frequency array for characters, then compare mirrored indices from both ends of the alphabet. Python uses a list of size 26, Java uses an int[26] array, and C++ uses a vector<int>(26). All versions achieve O(n) time complexity.
How to solve Mirror Frequency Distance in O(n)?
Traverse the string once and store frequencies of each character. Then compute the mirror of each letter using the alphabet relationship (for example 'z' - (c - 'a')). Compare the counts of mirrored pairs and accumulate the required distance. Because each character is processed once, the total complexity stays O(n).
What is the best approach for Mirror Frequency Distance?
The most efficient approach counts character frequencies in a single pass using a 26-length array or hash map. After counting, compare each character's frequency with its alphabet mirror (a-z, b-y, etc.). This solution runs in O(n) time and O(1) space for lowercase English strings.
Is Mirror Frequency Distance asked at Google/Amazon/Meta?
Problems involving character frequency tables and mirror relationships appear frequently in interviews at companies like Amazon and Google. While the exact title may vary, the underlying concepts—hash tables, string counting, and constant-time lookups—are common interview patterns.
What data structure is used in Mirror Frequency Distance?
The core data structure is a frequency table. This can be implemented with a hash map for general character sets or a fixed array of size 26 for lowercase English letters. The array version is typically preferred because it provides constant-time indexing with minimal memory.
What is the time complexity of Mirror Frequency Distance?
The optimal solution runs in O(n) time where n is the length of the string. A single pass counts character frequencies, followed by a constant-size loop over 13 mirror pairs. Space complexity is O(1) when using a fixed array for the 26 letters.

Ready to solve this problem?

Practice Mirror Frequency Distance with our built-in code editor and test cases.

Practice on FleetCode
Previous

Two Sum

Next

Longest Substring Without Repeating Characters