Find Mirror Score of a String

Find Mirror Score of a String

What is this problem about?

The Find Mirror Score of a String interview question is a simulation and string matching problem. A character's "mirror" is its opposite in the alphabet (e.g., 'a' mirrors 'z', 'b' mirrors 'y'). As you iterate through a string, for each character $s[i]$, you look for its mirror character at a previous index $j < i$ that hasn't been "used" yet. If multiple exist, you pick the one closest to $i$. The "score" is the sum of the distances $(i - j)$ for all such matched pairs.

Why is this asked in interviews?

Companies like Carwale use this to test your proficiency with Hash Tables and Stacks. It’s a variation of the "Valid Parentheses" problem but applied to alphabet mirrors. It evaluates whether you can efficiently manage "unmatched" characters and retrieve the most recent occurrence of a specific target.

Algorithmic pattern used

This problem is solved using the Hash Table of Stacks pattern.

1. Mirror Map: Pre-calculate or use a formula to find mirror characters: mirror(c) = 'z' - (c - 'a').
2. Storage: Use a hash map where the key is a character and the value is a Stack of indices where that character has appeared but hasn't been matched yet.
3. Iterate: For each character at index $i$:
   • Calculate its mirror $m$.
   • Check if the stack for $m$ is non-empty.
   • If it is, pop the top index $j$, and add i - j to the total score.
   • If not, push the current index $i$ onto the stack for character $s[i]$.

Example explanation

String: "aczb"

1. index 0: 'a'. Mirror is 'z'. Stack for 'z' is empty. Push index 0 to stack['a'].
2. index 1: 'c'. Mirror is 'x'. Stack for 'x' is empty. Push index 1 to stack['c'].
3. index 2: 'z'. Mirror is 'a'. stack['a'] has [0]. Pop 0. Score += $2 - 0 = 2$.
4. index 3: 'b'. Mirror is 'y'. Stack for 'y' is empty. Push index 3 to stack['b']. Total Score: 2.

Common mistakes candidates make

• Linear Search: Searching backwards through the string for every character ($O(N^2)$), which fails for long strings.
• Using a Queue: Using a FIFO structure instead of a Stack. The problem usually specifies the closest previous index, which requires LIFO behavior.
• Incorrect Mirroring: Mistakes in the ASCII math required to find the mirror character.

Interview preparation tip

Whenever you need to "match" an element with the "most recent" occurrence of something else, think of a Stack. Storing these stacks inside a Hash Map is a powerful way to handle multiple categories of "things to match" simultaneously. This is a common String interview pattern.