Find Mirror Score of a String

Med

#3032Time: O(n^2), where `n` is the length of the string. The nested loops lead to a quadratic time complexity, as for each element `i`, we might scan up to `i` elements before it.Space: O(n) to store the `marked` boolean array.1 company

Data structures

Hash Table String Stack

Companies

carwale

Prompt

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 <= 10⁵
s consists only of lowercase English letters.

Approaches

2 approaches with complexity analysis and trade-offs.

This approach directly simulates the process described in the problem statement. We iterate through each character of the string and, for each one, we search backwards through the previously seen characters to find a suitable mirror pair. A boolean array is used to keep track of which characters have already been marked and paired.

Algorithm

Initialize score = 0 and a boolean array marked of size n to false.
Loop through the string s with index i from 0 to n-1.
Calculate the mirror character for s[i].
Start a nested loop with index j from i-1 down to 0.
Inside the inner loop, check if j is unmarked and s[j] is the mirror of s[i].
If a match is found:
- Add i - j to score.
- Set marked[i] and marked[j] to true.
- Break the inner loop.
After the outer loop finishes, return score.

Walkthrough

We'll maintain a boolean array marked of the same size as the input string s, initialized to all false. This array helps us track which indices have been used in a mirror pair.

We iterate through the string from left to right, using an index i. For each character s[i], we determine its mirror character. Then, we perform a nested loop, iterating backwards from j = i - 1 down to 0. This backward iteration ensures that we find the closest valid index j first.

In the inner loop, we check if the index j is unmarked (marked[j] is false) and if s[j] is the mirror of s[i]. If we find such a j, we add the difference i - j to our total score, mark both indices i and j as used by setting marked[i] = true and marked[j] = true, and then break the inner loop to proceed to the next i.

If the inner loop completes without finding a match, we do nothing and move to the next i. After iterating through the entire string, the accumulated score is the result.

1class Solution {2    public long findMirrorScore(String s) {3        int n = s.length();4        boolean[] marked = new boolean[n];5        long score = 0;6 7        for (int i = 0; i < n; i++) {8            char mirrorChar = (char) ('a' + ('z' - s.charAt(i)));9            // Search for the closest unmarked mirror character j < i10            for (int j = i - 1; j >= 0; j--) {11                if (!marked[j] && s.charAt(j) == mirrorChar) {12                    score += (long) (i - j);13                    marked[i] = true;14                    marked[j] = true;15                    break; // Found the closest one, move to next i16                }17            }18        }19        return score;20    }21}

Complexity

Time

O(n^2), where `n` is the length of the string. The nested loops lead to a quadratic time complexity, as for each element `i`, we might scan up to `i` elements before it.

Space

O(n) to store the `marked` boolean array.

Trade-offs

Pros

Simple to understand and implement as it directly follows the problem description.

Cons

Inefficient for large inputs. With n up to 10^5, an O(n^2) solution will be too slow and result in a "Time Limit Exceeded" error.

This approach optimizes the search for a mirror pair by using a more efficient data structure. Instead of re-scanning previous elements for each character, we maintain a collection of stacks, one for each letter of the alphabet. These stacks store the indices of characters that are available to be paired. This allows us to find the closest mirror match in constant time.

Algorithm

Create an array of 26 deques (or stacks), positions, one for each letter of the alphabet.
Initialize score = 0.
Loop through the string s with index i from 0 to n-1.
Let currentChar = s[i] and mirrorChar be its mirror.
Check if the stack for mirrorChar, positions[mirrorChar - 'a'], is empty.
If it's not empty:
- Pop an index j from the stack.
- Add i - j to score.
If it is empty:
- Push the current index i onto the stack for currentChar, positions[currentChar - 'a'].
After the loop, return score.

Walkthrough

The key observation is that for any index i, the "closest" unmarked index j < i is simply the most recent one we've encountered. This "Last-In, First-Out" (LIFO) behavior is perfectly modeled by a stack.

We use an array of stacks, say positions, of size 26. positions[c - 'a'] will store the indices of all occurrences of character c that are currently unmarked and available for pairing.

We iterate through the string s from left to right with index i. For the character s[i], we find its mirror, mirrorChar. We then check the stack corresponding to mirrorChar, i.e., positions[mirrorChar - 'a'].

If this stack is not empty, it means there's an available character to form a pair. The index at the top of the stack is the most recent (and thus largest) j < i, which is exactly what we need. We pop this index j, calculate i - j, add it to the score, and we're done with this pair.

If the stack for mirrorChar is empty, no match can be made at this time. The current character s[i] at index i is now a candidate for a future pair. So, we push its index i onto its own character's stack, positions[s.charAt(i) - 'a']. This single pass through the string efficiently pairs up characters and calculates the score.

1import java.util.ArrayDeque;2import java.util.Deque;3 4class Solution {5    public long findMirrorScore(String s) {6        // Array of Deques (acting as stacks) to store indices for each character7        Deque<Integer>[] positions = new ArrayDeque[26];8        for (int i = 0; i < 26; i++) {9            positions[i] = new ArrayDeque<>();10        }11 12        long score = 0;13        int n = s.length();14 15        for (int i = 0; i < n; i++) {16            char currentChar = s.charAt(i);17            char mirrorChar = (char) ('a' + ('z' - currentChar));18            int mirrorCharIndex = mirrorChar - 'a';19 20            // Check if there's an available mirror character21            if (!positions[mirrorCharIndex].isEmpty()) {22                // Found a match. The top of the stack is the closest (largest) j < i.23                int j = positions[mirrorCharIndex].pop();24                score += (long) (i - j);25            } else {26                // No match found, so this character becomes available for future matches.27                int currentCharIndex = currentChar - 'a';28                positions[currentCharIndex].push(i);29            }30        }31        return score;32    }33}

Complexity

Time

O(n), where `n` is the length of the string. We iterate through the string once, and each operation inside the loop (stack push/pop, array access) takes constant time.

Space

O(n) in the worst case. If the string contains no mirror pairs (e.g., "abcde"), every index will be pushed onto a stack. The total number of elements stored across all stacks will be `n`. The space for the array of stacks itself is `O(k)` where `k` is the alphabet size (26), which is constant.

Trade-offs

Pros

Highly efficient with linear time complexity, making it suitable for large inputs.
Elegant solution that correctly identifies the "closest" match property using a stack.

Cons

Uses O(n) auxiliary space, which might be a concern for extremely memory-constrained environments, although it's standard for this type of problem.

Solutions

Solution

1class Solution {2public3  long calculateScore(String s) {4    Map<Character, List<Integer>> d = new HashMap<>(26);5    int n = s.length();6    long ans = 0;7    for (int i = 0; i < n; ++i) {8      char x = s.charAt(i);9      char y = (char)('a' + 'z' - x);10      if (d.containsKey(y)) {11        var ls = d.get(y);12        int j = ls.remove(ls.size() - 1);13        if (ls.isEmpty()) {14          d.remove(y);15        }16        ans += i - j;17      } else {18        d.computeIfAbsent(x, k->new ArrayList<>()).add(i);19      }20    }21    return ans;22  }23}

1class Solution {2public:3  long long calculateScore(string s) {4    unordered_map<char, vector<int>> d;5    int n = s.length();6    long long ans = 0;7    for (int i = 0; i < n; ++i) {8      char x = s[i];9      char y = 'a' + 'z' - x;10      if (d.contains(y)) {11        vector<int> &ls = d[y];12        int j = ls.back();13        ls.pop_back();14        if (ls.empty()) {15          d.erase(y);16        }17        ans += i - j;18      } else {19        d[x].push_back(i);20      }21    }22    return ans;23  }24};

1class Solution:2    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 ans

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem