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:
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.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 <= 105s consists only of lowercase English letters.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.
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.
Python
Java
C++
Go
TypeScript
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Backward Scan | O(n²) | O(n) | Useful for understanding the pairing rule or when constraints are very small |
| Hash Table + Stack | O(n) | O(n) | Optimal solution for large inputs and typical interview expectations |
3412. Find Mirror Score of a String | Stack | HashMap • Aryan Mittal • 1,341 views views
Watch 6 more video solutions →Practice Find Mirror Score of a String with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor