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 (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.

3889. Mirror Frequency Distance - Practice Online

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