Find Mirror Score of a String

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.

Examples

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^5
• s consists only of lowercase English letters.

Solution

Method 1 – Stack and Hash Map for Mirror Matching

Intuition

We need to efficiently find the closest unmarked mirror character to the left for each character. By mapping each character to its mirror and using a stack for each mirror character, we can quickly find and mark pairs as we iterate.

Approach

1. Build a mirror mapping for all lowercase letters: mirror of 'a' is 'z', ..., mirror of 'z' is 'a'.
2. Use a stack for each character to store indices of unmarked occurrences.
3. Iterate through the string from left to right:
   • For each character at index i, check if the stack for its mirror character is non-empty.
   • If so, pop the top index j from the stack, mark both i and j, and add i-j to the score.
   • Otherwise, push i onto the stack for this character.
4. Return the total score.

Code

C++

class Solution {
public:
    int mirrorScore(string s) {
        unordered_map<char, char> mirror;
        for (char c = 'a'; c <= 'z'; ++c) mirror[c] = 'z' - (c - 'a');
        unordered_map<char, stack<int>> stks;
        int ans = 0;
        vector<bool> marked(s.size(), false);
        for (int i = 0; i < s.size(); ++i) {
            char m = mirror[s[i]];
            if (!stks[m].empty()) {
                int j = stks[m].top(); stks[m].pop();
                ans += i - j;
            } else {
                stks[s[i]].push(i);
            }
        }
        return ans;
    }
};

Go

func mirrorScore(s string) int {
    mirror := map[byte]byte{}
    for c := byte('a'); c <= 'z'; c++ {
        mirror[c] = 'z' - (c - 'a')
    }
    stks := map[byte][]int{}
    ans := 0
    for i := 0; i < len(s); i++ {
        m := mirror[s[i]]
        if len(stks[m]) > 0 {
            j := stks[m][len(stks[m])-1]
            stks[m] = stks[m][:len(stks[m])-1]
            ans += i - j
        } else {
            stks[s[i]] = append(stks[s[i]], i)
        }
    }
    return ans
}

Java

class Solution {
    public int mirrorScore(String s) {
        Map<Character, Character> mirror = new HashMap<>();
        for (char c = 'a'; c <= 'z'; c++) mirror.put(c, (char)('z' - (c - 'a')));
        Map<Character, Deque<Integer>> stks = new HashMap<>();
        int ans = 0;
        for (int i = 0; i < s.length(); i++) {
            char m = mirror.get(s.charAt(i));
            stks.putIfAbsent(m, new ArrayDeque<>());
            stks.putIfAbsent(s.charAt(i), new ArrayDeque<>());
            if (!stks.get(m).isEmpty()) {
                int j = stks.get(m).pop();
                ans += i - j;
            } else {
                stks.get(s.charAt(i)).push(i);
            }
        }
        return ans;
    }
}

Kotlin

class Solution {
    fun mirrorScore(s: String): Int {
        val mirror = ('a'..'z').associateWith { 'z' - (it - 'a') }
        val stks = mutableMapOf<Char, ArrayDeque<Int>>()
        var ans = 0
        for (i in s.indices) {
            val m = mirror[s[i]]!!
            stks.putIfAbsent(m, ArrayDeque())
            stks.putIfAbsent(s[i], ArrayDeque())
            if (stks[m]!!.isNotEmpty()) {
                val j = stks[m]!!.removeLast()
                ans += i - j
            } else {
                stks[s[i]]!!.addLast(i)
            }
        }
        return ans
    }
}

Python

class Solution:
    def mirrorScore(self, s: str) -> int:
        mirror = {chr(ord('a')+i): chr(ord('z')-i) for i in range(26)}
        stks = {c: [] for c in mirror}
        ans = 0
        for i, c in enumerate(s):
            m = mirror[c]
            if stks[m]:
                j = stks[m].pop()
                ans += i - j
            else:
                stks[c].append(i)
        return ans

Rust

impl Solution {
    pub fn mirror_score(s: String) -> i32 {
        let mirror: Vec<char> = (0..26).map(|i| (b'z' - i) as char).collect();
        let mut stks: Vec<Vec<usize>> = vec![vec![]; 26];
        let s = s.as_bytes();
        let mut ans = 0;
        for (i, &c) in s.iter().enumerate() {
            let idx = (c - b'a') as usize;
            let m = (b'z' - (c - b'a')) as usize - b'a' as usize;
            if !stks[m].is_empty() {
                let j = stks[m].pop().unwrap();
                ans += i - j;
            } else {
                stks[idx].push(i);
            }
        }
        ans as i32
    }
}

TypeScript

class Solution {
    mirrorScore(s: string): number {
        const mirror: Record<string, string> = {};
        for (let i = 0; i < 26; i++) {
            mirror[String.fromCharCode(97+i)] = String.fromCharCode(122-i);
        }
        const stks: Record<string, number[]> = {};
        for (let i = 0; i < 26; i++) stks[String.fromCharCode(97+i)] = [];
        let ans = 0;
        for (let i = 0; i < s.length; i++) {
            const c = s[i];
            const m = mirror[c];
            if (stks[m].length) {
                const j = stks[m].pop()!;
                ans += i - j;
            } else {
                stks[c].push(i);
            }
        }
        return ans;
    }
}

Complexity

• ⏰ Time complexity: O(n), where n is the length of s. Each character is processed once.
• 🧺 Space complexity: O(n), for the stacks used to track indices.