Find Mirror Score of a String

medium stack string simulation

Problem

The mirror of a letter is its partner when the alphabet is reversed: mirror of 'a' is 'z', of 'b' is 'y', and so on. Starting with score 0, scan s left to right. At each index i, find the closest unmarked index j < i with s[j] equal to the mirror of s[i]; if it exists, mark both i and j and add i − j to the score. Return the final score.

Inputs = "aczzx"

Output5

At i=2 ('z'), mirror is 'a' at j=0 → +2. At i=4 ('x'), mirror is 'c' at j=1 → +3. Total = 5.

s (lowercase letters)

def calculateScore(s):
    stacks = [[] for _ in range(26)]    # unmarked indices per letter
    score = 0
    for i in range(len(s)):
        c = ord(s[i]) - ord('a')        # 0..25 for this letter
        mirror = 25 - c                 # the mirror letter's index
        if stacks[mirror]:              # closest unmarked mirror waiting?
            j = stacks[mirror].pop()    # take it; mark both i and j
            score += i - j              # add the index gap
        else:
            stacks[c].append(i)         # leave i unmarked for later
    return score

function calculateScore(s) {
  const stacks = Array.from({ length: 26 }, () => []);
  let score = 0;
  for (let i = 0; i < s.length; i++) {
    const c = s.charCodeAt(i) - 97;     // 0..25 for this letter
    const mirror = 25 - c;              // the mirror letter's index
    if (stacks[mirror].length) {        // closest unmarked mirror waiting?
      const j = stacks[mirror].pop();   // take it; mark both i and j
      score += i - j;                   // add the index gap
    } else {
      stacks[c].push(i);                // leave i unmarked for later
    }
  }
  return score;
}

long calculateScore(String s) {
    Deque<Integer>[] stacks = new ArrayDeque[26];
    for (int k = 0; k < 26; k++) stacks[k] = new ArrayDeque<>();
    long score = 0;
    for (int i = 0; i < s.length(); i++) {
        int c = s.charAt(i) - 'a';       // 0..25 for this letter
        int mirror = 25 - c;             // the mirror letter's index
        if (!stacks[mirror].isEmpty()) { // closest unmarked mirror?
            int j = stacks[mirror].pop();// take it; mark both i and j
            score += i - j;              // add the index gap
        } else {
            stacks[c].push(i);           // leave i unmarked for later
        }
    }
    return score;
}

long long calculateScore(string s) {
    vector<vector<int>> stacks(26);       // unmarked indices per letter
    long long score = 0;
    for (int i = 0; i < (int)s.size(); i++) {
        int c = s[i] - 'a';              // 0..25 for this letter
        int mirror = 25 - c;             // the mirror letter's index
        if (!stacks[mirror].empty()) {   // closest unmarked mirror?
            int j = stacks[mirror].back();
            stacks[mirror].pop_back();   // take it; mark both i and j
            score += i - j;              // add the index gap
        } else {
            stacks[c].push_back(i);      // leave i unmarked for later
        }
    }
    return score;
}

Explanation

The naive reading of the problem — for each i, search backward for the closest unmarked mirror — is quadratic. The key observation is that "closest unmarked earlier index" is exactly what a stack gives you: among unmarked positions, the most recent one is on top.

So we keep 26 stacks, one per letter, each holding the indices of that letter that are still unmarked, in increasing order. When we reach index i with letter s[i], its mirror is the letter at alphabet index 25 - c. The closest unmarked occurrence of that mirror letter is simply the top of stacks[mirror].

If that stack is non-empty, we pop its top index j — this marks both i and j at once (popping removes j from consideration, and we never push i) — and add i − j to the running score.

If no mirror is waiting, i stays unmarked, so we push it onto its own letter's stack stacks[c], where a future mirror letter can find it.

Example s = "aczzx": indices 0 ('a') and 1 ('c') find no mirror and are pushed. At index 2 ('z') the mirror is 'a', whose stack has 0 → pop, score += 2. At index 3 ('z') the mirror 'a' stack is now empty → push 3. At index 4 ('x') the mirror is 'c', whose stack has 1 → pop, score += 3. Total 2 + 3 = 5.

Time: O(n) Space: O(n)