LeetCode Problem 3412

Difficulty: 🟡 Medium
Topics: Hash Table, String, Stack, Simulation

Solution

LeetCode 3412 - Find Mirror Score of a String

Problem Understanding

We are given a lowercase English string s. Every letter has a unique "mirror" letter obtained by reversing the alphabet.

For example:

• 'a' ↔ 'z'
• 'b' ↔ 'y'
• 'c' ↔ 'x'

and so on.

We process the string from left to right. For each position i, we want to find the closest unmarked position j to its left such that:

• j < i
• s[j] is the mirror character of s[i]
• index j has not already been matched and marked

If such a position exists, we:

• mark both i and j
• add i - j to the score

If no valid position exists, we simply continue.

The goal is to return the total score after the entire string has been processed.

The important detail is the phrase closest unmarked index. Suppose multiple unmatched mirror characters exist to the left. We must choose the one with the largest index because it is the closest.

The constraint s.length <= 10^5 is large enough that quadratic solutions will time out. We need a solution that processes the string efficiently, ideally in linear time.

Several edge cases are worth noting:

• A string with no mirror pairs should return 0.
• Multiple possible mirror matches may exist, and we must always choose the closest unmarked one.
• Once an index becomes marked, it can never participate in another pair.
• The string may contain many occurrences of the same character, requiring efficient tracking of unmatched positions.
• The answer can become large, so we should accumulate it using a 64-bit integer type. In Python this happens automatically, while in Go we should use int64.

Approaches

Brute Force

A direct simulation follows the problem statement literally.

For every index i:

1. Compute its mirror character.
2. Scan leftward from i - 1 down to 0.
3. Find the first unmarked index containing the mirror character.
4. Mark both indices and add the distance.

This approach is correct because it exactly implements the rules of the problem. The first valid index found while scanning backward is automatically the closest one.

However, in the worst case we may scan nearly the entire prefix for every position. With up to 10^5 characters, this leads to quadratic complexity, which is far too slow.

Optimal Approach

The key observation is that for each character we only need access to the closest unmatched occurrence of its mirror character.

Suppose we are currently processing character c.

If its mirror is m, then among all unmatched positions containing m, we need the most recent one because that is the closest valid index.

This behavior is exactly what a stack provides.

For each character, maintain a stack of unmatched indices where that character appeared.

When processing position i:

• Compute its mirror character.

• If the mirror character's stack is non-empty:

• Pop the top index.

• This top index is the closest unmatched mirror position.

• Add the distance to the answer.

• Otherwise:

• Store the current index in the stack corresponding to s[i].

Because indices are pushed in increasing order, the top of the stack always represents the closest unmatched occurrence.

Each index is pushed once and popped at most once, giving linear complexity.

Approach Comparison

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n²)	O(n)	Direct simulation with backward scans
Optimal	O(n)	O(n)	Uses stacks to track unmatched positions of each character

Algorithm Walkthrough

1. Create a collection of stacks, one stack for each character.
2. Initialize score = 0.
3. Iterate through the string from left to right using index i.
4. Let the current character be c = s[i].
5. Compute its mirror character. Since lowercase letters are consecutive in ASCII, the mirror of c can be computed as:

mirror = chr(ord('a') + ord('z') - ord(c)) 6. Check the stack corresponding to mirror. 7. If that stack is not empty:

• Pop the top index j.
• This is the closest unmatched mirror occurrence.
• Add i - j to the score.
• Do not store the current index because both positions are now marked.

8. Otherwise:

• No unmatched mirror exists.
• Push the current index i onto the stack corresponding to c.
• This index becomes available for future matches.

9. After processing all characters, return the accumulated score.

Why it works

The crucial invariant is that each stack contains exactly the unmatched occurrences of a character, stored in increasing index order.

When processing index i, the valid match must be the closest unmatched mirror occurrence to the left. Since indices are pushed as they appear, the most recent unmatched occurrence is always at the top of the corresponding stack. Popping from the stack therefore selects exactly the index required by the problem statement. Because matched indices are immediately removed, they can never be reused. Thus every pairing performed by the algorithm is identical to the pairing defined by the problem, guaranteeing correctness.

Python Solution

from collections import defaultdict
from typing import List

class Solution:
    def calculateScore(self, s: str) -> int:
        stacks = defaultdict(list)
        score = 0

        for i, ch in enumerate(s):
            mirror = chr(ord('a') + ord('z') - ord(ch))

            if stacks[mirror]:
                j = stacks[mirror].pop()
                score += i - j
            else:
                stacks[ch].append(i)

        return score

The implementation maintains a dictionary from character to a stack of unmatched indices.

For each character, we compute its mirror character in constant time. If the mirror stack contains indices, we pop the most recent unmatched occurrence and immediately add the distance to the answer. Otherwise, the current index is stored in its own character stack for potential future matching.

The dictionary only stores unmatched positions, so every index enters the structure once and leaves it at most once. This directly implements the stack-based algorithm described above.

Go Solution

func calculateScore(s string) int64 {
	stacks := make([][]int, 26)
	var score int64

	for i, ch := range s {
		idx := int(ch - 'a')
		mirror := 25 - idx

		if len(stacks[mirror]) > 0 {
			stack := stacks[mirror]
			j := stack[len(stack)-1]
			stacks[mirror] = stack[:len(stack)-1]

			score += int64(i - j)
		} else {
			stacks[idx] = append(stacks[idx], i)
		}
	}

	return score
}

The Go version uses a fixed array of 26 stacks because only lowercase English letters are possible. This avoids hash table overhead and provides constant-time access to each character's stack.

The score is stored as int64 because the sum of distances can exceed the range of a 32-bit integer. Empty slices naturally serve as empty stacks, so no special nil handling is required.

Worked Examples

Example 1

Input: s = "aczzx"

Mirror relationships:

• a ↔ z
• c ↔ x

i	char	mirror	Action	Stacks After Action	Score
0	a	z	No unmatched z, push 0 into a	a:[0]	0
1	c	x	No unmatched x, push 1 into c	a:[0], c:[1]	0
2	z	a	Pop 0 from a	c:[1]	2
3	z	a	No unmatched a, push 3 into z	c:[1], z:[3]	2
4	x	c	Pop 1 from c	z:[3]	5

Final score = 5

Example 2

Input: s = "abcdef"

i	char	mirror	Action	Score
0	a	z	Push	0
1	b	y	Push	0
2	c	x	Push	0
3	d	w	Push	0
4	e	v	Push	0
5	f	u	Push	0

No mirror pairs are ever found.

Final score = 0

Additional Example

Input: s = "azaz"

i	char	Action	Score
0	a	Push 0	0
1	z	Match with 0	1
2	a	Push 2	1
3	z	Match with 2	2

Final score = 2

Notice that the stack naturally ensures that the closest unmatched occurrence is chosen.

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n)	Each index is pushed once and popped at most once
Space	O(n)	In the worst case all indices remain unmatched and are stored in stacks

The algorithm performs a constant amount of work for each character. Since every index can only be inserted into a stack once and removed once, the total work across all stack operations is linear. The storage requirement is linear because, in the worst case, every character could remain unmatched.

Test Cases

sol = Solution()

assert sol.calculateScore("aczzx") == 5      # provided example
assert sol.calculateScore("abcdef") == 0     # no mirror pairs

assert sol.calculateScore("a") == 0          # single character
assert sol.calculateScore("az") == 1         # simplest mirror pair
assert sol.calculateScore("za") == 1         # reverse ordering still matches

assert sol.calculateScore("azaz") == 2       # multiple independent matches
assert sol.calculateScore("zzzaaa") == 9     # repeated characters

assert sol.calculateScore("abcxyz") == 9     # three mirror matches
assert sol.calculateScore("aaaa") == 0       # no matching mirrors
assert sol.calculateScore("zzzz") == 0       # no matching mirrors

assert sol.calculateScore("abzy") == 4       # two separate matches
assert sol.calculateScore("yxba") == 4       # mirrors appear first

assert sol.calculateScore("abccba") == 0     # no mirror relationships
assert sol.calculateScore("azyx") == 2       # one match, others unmatched

Test Summary

Test	Why
"aczzx"	Official example with multiple matches
"abcdef"	Official example with no matches
"a"	Minimum length input
"az"	Smallest possible successful match
"za"	Mirror appears before matching character
"azaz"	Repeated matching pattern
"zzzaaa"	Multiple matches against repeated characters
"abcxyz"	Several different mirror pairs
"aaaa"	No mirror characters present
"zzzz"	Same character repeated without mirrors
"abzy"	Multiple independent pairings
"yxba"	Matching occurs after mirror characters are stored
"abccba"	Similar-looking characters but no mirror pairs
"azyx"	Mix of matched and unmatched positions

Edge Cases

Single Character String

A string of length one can never form a pair because there is no earlier index to match with. A naive implementation might accidentally attempt a lookup or pairing operation without checking availability. The stack-based solution simply pushes the index and finishes, returning zero.

Multiple Candidate Mirror Positions

Consider "aaaz". When processing the final 'z', there are three unmatched 'a' positions available. The problem requires choosing the closest one, which is the most recent unmatched 'a'. The stack structure naturally enforces this rule because the newest unmatched occurrence is always on top and is popped first.

Characters That Never Find a Match

Strings such as "abcdef" contain no mirror pairs at all. All indices remain stored in their respective stacks until the end. The algorithm handles this naturally, never performing any pops and returning a score of zero.

Large Inputs With Many Matches

For strings approaching length 100000, a quadratic search would be too slow. The stack-based approach ensures each index participates in at most one push and one pop operation, keeping the runtime linear even for the largest valid inputs.

Repeated Matching and Unmatching Patterns

Inputs such as "azazazaz" repeatedly create and consume stack entries. A bug-prone implementation might accidentally reuse already matched positions. Because matched indices are immediately removed from their stack when popped, the algorithm guarantees that every index is used at most once.