#3412

Medium

auto_awesomeStack-based state management

LeetCode Problem Workspace

Find Mirror Score of a String

Calculate the mirror score of a string using stack-based state management for matching letters efficiently and accurately.

hash table string stack simulation

Problem Statement

Given a string s of lowercase English letters, compute its mirror score. The mirror of a letter is defined as its corresponding letter in the reversed alphabet: 'a' maps to 'z', 'b' maps to 'y', and so on.

Initially, all characters in s are unmarked. For each character, find if a previously unmarked character exists such that it forms a mirror pair. Count all such valid mirror pairs to return the total mirror score.

Examples

Example 1

Input: s = "aczzx"

Output: 5

Example 2

Input: s = "abcdef"

Output: 0

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.

Solution Approach

Map each letter to its mirror

Create a simple hash table mapping every lowercase letter to its alphabetic mirror. This prepares direct lookup for each character during the stack processing, reducing repeated computations.

Use stacks to track unmatched letters

Maintain a stack for each character to track its unpaired positions. When encountering a character, check if its mirror stack is non-empty. If so, pop from the mirror stack and increment the score; otherwise, push the current character onto its stack.

Single-pass computation

Iterate through the string once, updating stacks and the score on the fly. This stack-based simulation avoids nested loops and guarantees efficient linear-time execution while keeping space proportional to the number of unique letters.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time complexity is O(n) for n = s.length due to the single-pass iteration and constant-time stack operations. Space complexity is O(1) relative to input size because only 26 stacks for lowercase letters are maintained.

What Interviewers Usually Probe

Focus on the stack-based state management pattern for mirror matching.
Ask about handling unmarked letters and simultaneous updates to stacks.
Probe edge cases with repeated letters or no mirror pairs.

Common Pitfalls or Variants

Common pitfalls

Failing to map letters correctly to their mirror equivalents.
Forgetting to check the corresponding mirror stack before pushing the current character.
Using nested loops instead of stacks, leading to O(n^2) performance.

Follow-up variants

Compute mirror scores with uppercase and lowercase letters combined.
Modify the problem to allow partial mirror pairs with a tolerance of one mismatch.
Calculate maximum mirror score after deleting at most k characters from s.

FAQ

What exactly is the mirror score of a string?

The mirror score is the total number of letter pairs in the string where each letter matches the alphabetic mirror of another unmarked letter.

How do stacks help in computing mirror score?

Stacks maintain the positions of unmatched letters, enabling O(1) pairing checks with incoming characters instead of scanning the string repeatedly.

Can this approach handle very long strings efficiently?

Yes, because the algorithm iterates through the string once and uses a fixed number of stacks, ensuring linear time and constant extra space.

What should I watch out for when mapping letters to mirrors?

Ensure the mapping correctly pairs 'a' with 'z', 'b' with 'y', etc., and consistently uses lowercase letters for indexing stacks.

Is the stack-based state management pattern always needed for mirror score problems?

For this problem, it is essential to efficiently track unmatched letters and pair mirrors without scanning the entire string repeatedly.

terminal

Solution

Solution 1: Hash Table

We can use a hash table $\textit{d}$ to store the index list of each unmarked character, where the key is the character and the value is the list of indices.

1

2

3

4

5

6

7

8

9

10

11

12

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

Continue Practicing

#3522 calculate score after performing instructions #3561 resulting string after adjacent removals #3597 partition string