Skip to main content
Talentd

Find Mirror Score of a String - Solution & Explanation

MediumHash TableStringStackSimulation8 min readAsked at: Amazon, Google, Carwale
Practice this problem

Problem Statement

You are given a string s.

We define the mirror of a letter in the English alphabet as its corresponding letter when the alphabet is reversed. For example, the mirror of 'a' is 'z', and the mirror of 'y' is 'b'.

Initially, all characters in the string s are unmarked.

You start with a score of 0, and you perform the following process on the string s:

  • Iterate through the string from left to right.
  • At each index i, find the closest unmarked index j such that j < i and s[j] is the mirror of s[i]. Then, mark both indices i and j, and add the value i - j to the total score.
  • If no such index j exists for the index i, move on to the next index without making any changes.

Return the total score at the end of the process.

 

Example 1:

Input: s = "aczzx"

Output: 5

Explanation:

  • i = 0. There is no index j that satisfies the conditions, so we skip.
  • i = 1. There is no index j that satisfies the conditions, so we skip.
  • i = 2. The closest index j that satisfies the conditions is j = 0, so we mark both indices 0 and 2, and then add 2 - 0 = 2 to the score.
  • i = 3. There is no index j that satisfies the conditions, so we skip.
  • i = 4. The closest index j that satisfies the conditions is j = 1, so we mark both indices 1 and 4, and then add 4 - 1 = 3 to the score.

Example 2:

Input: s = "abcdef"

Output: 0

Explanation:

For each index i, there is no index j that satisfies the conditions.

 

Constraints:

  • 1 <= s.length <= 105
  • s consists only of lowercase English letters.

Approach Overview

Problem Overview: You are given a string s. For every character, its mirror is the character symmetric in the alphabet (a ↔ z, b ↔ y, etc.). While scanning the string, pair a character with a previous unmatched index containing its mirror. Each pair contributes the distance between indices to the total score.

Approach 1: Brute Force Simulation (O(n²) time, O(n) space)

Scan the string from left to right. For each index i, compute its mirror character using mirror = 'a' + 'z' - s[i]. Search backwards to find the closest previous unmatched index with that mirror character. If found, mark both indices as used and add i - j to the score. This approach directly simulates the rule but requires repeated backward scans, leading to quadratic time. It works for small inputs but does not scale well.

Approach 2: Hash Table + Stack (O(n) time, O(n) space)

Track unmatched indices using a hash table where each character maps to a stack of positions. Iterate through the string once. For the current character c, compute its mirror m. If the stack for m is not empty, pop the most recent index j and add i - j to the score. Otherwise, push the current index i onto the stack for c. The stack ensures the closest valid match is used, which matches the greedy pairing rule.

The key insight is that each index is pushed and popped at most once. Hash lookups and stack operations are constant time, so the entire process runs in linear time. This technique combines ideas from hash tables, stacks, and direct string simulation.

Recommended for interviews: The hash table + stack approach is the expected solution. It demonstrates that you recognize mirror character relationships and manage unmatched positions efficiently. Mentioning the brute force approach first shows you understand the pairing rule, but implementing the linear-time stack solution demonstrates stronger algorithmic thinking.

Solution

We can use a hash table d to store the index list of each unmarked character, where the key is the character and the value is the list of indices.

We traverse the string s, and for each character x, we find its mirror character y. If d contains y, we take out the index list ls corresponding to y, take out the last element j from ls, and remove j from ls. If ls becomes empty, we remove y from d. At this point, we have found a pair of indices (j, i) that meet the condition, and we add i - j to the answer. Otherwise, we add x to d.

The time complexity is O(n), and the space complexity is O(n). Here, n is the length of the string s.

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Brute Force Backward ScanO(n²)O(n)Useful for understanding the pairing rule or when constraints are very small
Hash Table + StackO(n)O(n)Optimal solution for large inputs and typical interview expectations

Video Solution

3412. Find Mirror Score of a String | Stack | HashMap • Aryan Mittal • 1,371 views views

Watch 8 more video solutions →

Frequently Asked Questions

Is Find Mirror Score of a String easy or hard?
The problem is rated Medium because the logic is simple once the mirror mapping is recognized, but many candidates initially attempt inefficient scans. Identifying the stack-based pairing strategy and implementing it in O(n) time is the key challenge.
Find Mirror Score of a String Python/Java solution
The typical implementation creates a dictionary or map from character to a stack of indices. During a single pass through the string, compute the mirror character and either pop from the mirror stack to add to the score or push the current index. This logic is straightforward to implement in Python, Java, C++, Go, or TypeScript.
How to solve Find Mirror Score of a String in O(n)?
Iterate through the string and maintain a hash map from character to a stack of indices. For each character c, compute its mirror m using 'a' + 'z' - c. If the stack for m is not empty, pop the previous index and add the distance to the score; otherwise push the current index. Each index is processed once, giving O(n) complexity.
What is the best approach for Find Mirror Score of a String?
The optimal approach uses a hash table combined with stacks. While iterating through the string, compute the mirror character (a↔z, b↔y, etc.). If an unmatched mirror index exists in the stack, pop it and add the distance between indices to the score; otherwise push the current index. This solution runs in O(n) time and O(n) space.
Is Find Mirror Score of a String asked at Google/Amazon/Meta?
Problems combining string processing with hash maps and stacks appear frequently in interviews at companies like Amazon, Google, and Meta. While the exact problem may vary, the pattern of pairing characters using a stack and constant-time lookups is a common interview theme.
What data structure is used in Find Mirror Score of a String?
The main data structures are a hash table and stacks. The hash table maps characters to stacks that store indices of unmatched occurrences. The stack structure ensures the most recent valid match is paired first, which satisfies the problem’s pairing rule.
What is the time complexity of Find Mirror Score of a String?
The optimal solution runs in O(n) time because each character index is pushed to a stack once and popped at most once. Hash lookups and stack operations are constant time. The space complexity is O(n) to store unmatched character indices.

Ready to solve this problem?

Practice Find Mirror Score of a String with our built-in code editor and test cases.

Practice on FleetCode
Previous

Two Sum

Next

Longest Substring Without Repeating Characters