Watch 7 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,341 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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.
| 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 |