Problem Description
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 iterate through the string, finding the closest unmarked index j for each index i such that j < i and s[j] is the mirror of s[i]. You mark both indices and add the value i - j to the total score. If no such index exists, you move on to the next index. Return the total score at the end of the process.
Key Insights
- The mirror of a character can be found by calculating its position relative to 'a' and mapping it to the corresponding character from 'z'.
- A stack can be used to keep track of unmarked indices that could potentially form valid pairs with future characters.
- The process involves iterating through the string and updating scores based on the closest unmarked index that matches the mirror condition.
Space and Time Complexity
Time Complexity: O(n), where n is the length of the string, since we iterate through the string once. Space Complexity: O(n), in the worst case, for the stack that stores indices.
Solution
The algorithm uses a stack to keep track of indices of unmarked characters. As we iterate through the string, we check if the current character's mirror exists in the stack. If it does, we pop the index from the stack, mark both indices, and update the score. If not, we simply push the current index onto the stack.