# Find Mirror Score of a String
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/find-mirror-score-of-a-string)
Canonical: https://scaleengineer.com/dsa/problems/find-mirror-score-of-a-string
**Data structures:** Hash Table, String, Stack
**Companies:** [carwale](https://scaleengineer.com/companies/carwale)
---
## 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** 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 <= 105`
* `s` consists only of lowercase English letters.

# Approaches
## Brute Force Simulation
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.
**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.
**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.
### Explanation
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.

```java
class Solution {
    public long findMirrorScore(String s) {
        int n = s.length();
        boolean[] marked = new boolean[n];
        long score = 0;

        for (int i = 0; i < n; i++) {
            char mirrorChar = (char) ('a' + ('z' - s.charAt(i)));
            // Search for the closest unmarked mirror character j < i
            for (int j = i - 1; j >= 0; j--) {
                if (!marked[j] && s.charAt(j) == mirrorChar) {
                    score += (long) (i - j);
                    marked[i] = true;
                    marked[j] = true;
                    break; // Found the closest one, move to next i
                }
            }
        }
        return score;
    }
}
```
### 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`.

## Optimized Single Pass using Stacks
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.
**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.
**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.
### Explanation
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.

```java
import java.util.ArrayDeque;
import java.util.Deque;

class Solution {
    public long findMirrorScore(String s) {
        // Array of Deques (acting as stacks) to store indices for each character
        Deque<Integer>[] positions = new ArrayDeque[26];
        for (int i = 0; i < 26; i++) {
            positions[i] = new ArrayDeque<>();
        }

        long score = 0;
        int n = s.length();

        for (int i = 0; i < n; i++) {
            char currentChar = s.charAt(i);
            char mirrorChar = (char) ('a' + ('z' - currentChar));
            int mirrorCharIndex = mirrorChar - 'a';

            // Check if there's an available mirror character
            if (!positions[mirrorCharIndex].isEmpty()) {
                // Found a match. The top of the stack is the closest (largest) j < i.
                int j = positions[mirrorCharIndex].pop();
                score += (long) (i - j);
            } else {
                // No match found, so this character becomes available for future matches.
                int currentCharIndex = currentChar - 'a';
                positions[currentCharIndex].push(i);
            }
        }
        return score;
    }
}
```
### 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`.

# Solutions
### Java

```java
class 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;
  }
}

```

### CPP

```cpp
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;
  }
};

```

### Python

```python
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 ans

```