Find Mirror Score of a String - Video Solutions
3412. Find Mirror Score of a String | Stack | HashMap
Find Mirror Score of a String - Video Solution
Watch 9 video solutions for Find Mirror Score of a String, a medium level problem involving Hash Table, String, Stack. This walkthrough by Aryan Mittal has 1,371 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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 indexjsuch thatj < iands[j]is the mirror ofs[i]. Then, mark both indicesiandj, and add the valuei - jto the total score. - If no such index
jexists for the indexi, 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 indexjthat satisfies the conditions, so we skip.i = 1. There is no indexjthat satisfies the conditions, so we skip.i = 2. The closest indexjthat satisfies the conditions isj = 0, so we mark both indices 0 and 2, and then add2 - 0 = 2to the score.i = 3. There is no indexjthat satisfies the conditions, so we skip.i = 4. The closest indexjthat satisfies the conditions isj = 1, so we mark both indices 1 and 4, and then add4 - 1 = 3to 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 <= 105sconsists 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.
Complexity Analysis
| 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 |