Find Mirror Score of a String solution and explanation
Google
8 more videos on this problem
3412. Find Mirror Score of a String | Stack | HashMapAryan Mittal · 9:14 · 1K views
Weekly Contest 431 |#leetcode |#WeeklyContest431 |Find Mirror Score of a StringHamsar · 0:50 · 205 views
3412. Find Mirror Score of a String (Leetcode Medium)Programming Live with Larry · 9:58 · 176 views
3412. Find Mirror Score of a String | Map | LeetCode | Medium | SetLeet's Code · 12:40 · 167 views
Find Mirror Score of a String | Leetcode daily challenge | Leetcode MediumBinaryMagic · 15:31 · 147 views
LeetCode Find Mirror Score of a String LeetCode 3412 LeetCodeR Sai Siddhu · 15:39 · 129 views
100476. Find Mirror Score of a String solution code|| Weekly contest-431 #leetcodeComputer Knowledge · 0:44 · 111 views
3412. Find Mirror score of a string leetcodeUnfiltered Programmer · 10:55 · 102 views
Leetcode 100476. Find Mirror Score of a StringAlgo Forces · 11:24 · 38 views
The problem
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.
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.
class Solution:
def calculateScore(self, s: str) -> int:
d = defaultdict(list)
ans = 0
for i, x in enumerate(s):
y = chr(ord("a") + ord("z") - ord(x))
if d[y]:
j = d[y].pop()
ans += i - j
else:
d[x].append(i)
return ansclass Solution {
public long calculateScore(String s) {
Map<Character, List<Integer>> d = new HashMap<>(26);
int n = s.length();
long ans = 0;
for (int i = 0; i < n; ++i) {
char x = s.charAt(i);
char y = (char) ('a' + 'z' - x);
if (d.containsKey(y)) {
var ls = d.get(y);
int j = ls.remove(ls.size() - 1);
if (ls.isEmpty()) {
d.remove(y);
}
ans += i - j;
} else {
d.computeIfAbsent(x, k -> new ArrayList<>()).add(i);
}
}
return ans;
}
}class Solution {
public:
long long calculateScore(string s) {
unordered_map<char, vector<int>> d;
int n = s.length();
long long ans = 0;
for (int i = 0; i < n; ++i) {
char x = s[i];
char y = 'a' + 'z' - x;
if (d.contains(y)) {
vector<int>& ls = d[y];
int j = ls.back();
ls.pop_back();
if (ls.empty()) {
d.erase(y);
}
ans += i - j;
} else {
d[x].push_back(i);
}
}
return ans;
}
};function calculateScore(s: string): number {
const d: Map<string, number[]> = new Map();
const n = s.length;
let ans = 0;
for (let i = 0; i < n; i++) {
const x = s[i];
const y = String.fromCharCode('a'.charCodeAt(0) + 'z'.charCodeAt(0) - x.charCodeAt(0));
if (d.has(y)) {
const ls = d.get(y)!;
const j = ls.pop()!;
if (ls.length === 0) {
d.delete(y);
}
ans += i - j;
} else {
if (!d.has(x)) {
d.set(x, []);
}
d.get(x)!.push(i);
}
}
return ans;
}func calculateScore(s string) (ans int64) {
d := make(map[rune][]int)
for i, x := range s {
y := 'a' + 'z' - x
if ls, ok := d[y]; ok {
j := ls[len(ls)-1]
d[y] = ls[:len(ls)-1]
if len(d[y]) == 0 {
delete(d, y)
}
ans += int64(i - j)
} else {
d[x] = append(d[x], i)
}
}
return
}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 |
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.