Problem Description

You are given a string s consisting of lowercase English letters.

The mirror of a letter is defined as its counterpart when the alphabet is reversed. For example:

• The mirror of 'a' is 'z' (first letter ↔ last letter)
• The mirror of 'b' is 'y' (second letter ↔ second-to-last letter)
• The mirror of 'c' is 'x', and so on

Initially, all characters in the string are unmarked. You need to process the string from left to right and calculate a score based on the following rules:

1. Iterate through each index i from left to right (starting from index 0)
2. For each index i, look for the closest unmarked index j where:
   • j < i (j must be to the left of i)
   • s[j] is the mirror of s[i]
3. If such an index j is found:
   • Mark both indices i and j as used (they cannot be paired again)
   • Add i - j to your total score
4. If no such index j exists, skip index i and continue

Return the total score after processing the entire string.

Example walkthrough:

For a string like "abcyxz":

• At index 3 ('y'), we can pair it with index 1 ('b') since 'b' is the mirror of 'y'. Score += 3 - 1 = 2
• At index 4 ('x'), we can pair it with index 2 ('c') since 'c' is the mirror of 'x'. Score += 4 - 2 = 2
• At index 5 ('z'), we can pair it with index 0 ('a') since 'a' is the mirror of 'z'. Score += 5 - 0 = 5
• Total score = 2 + 2 + 5 = 9

The key insight is that when multiple unmarked mirror characters exist to the left, we always choose the closest one (the one with the largest index that is still less than i).

Intuition

When we process the string from left to right, at each position i, we need to find the closest unmarked mirror character to its left. The key insight is that "closest" means we want the rightmost occurrence among all the unmarked mirror characters that appear before position i.

This naturally suggests using a data structure that can efficiently:

1. Store positions of unmarked characters
2. Retrieve the most recent (rightmost) position of a specific character
3. Remove a position once it's been marked

A hash table with lists is perfect for this. For each character, we maintain a list of its unmarked positions. When we need to find a mirror match, we look for the mirror character's list and take the last element (most recent position). This gives us the closest unmarked position automatically.

The clever part of the solution is that instead of storing both the character and its mirror separately, we can optimize by only storing positions when we can't find a match. Here's the key observation:

• When we encounter character x at position i, we check if its mirror y has any unmarked positions available
• If y has positions available, we found a match! We use the most recent one and add the score
• If y has no positions available, then x at position i might be a future match for some y that comes later, so we store position i under character x

This approach ensures that:

• We always pair with the closest (most recent) unmarked mirror character
• We efficiently manage the unmarked positions without explicitly tracking a "marked" status
• The time complexity is optimal since each position is processed at most twice (once when stored, once when matched)

The formula to calculate the mirror is elegant: for character x, its mirror is chr(ord('a') + ord('z') - ord(x)). This works because if x is the k-th letter from the start, its mirror is the k-th letter from the end.

Learn more about Stack patterns.

Solution Approach

The solution uses a hash table with lists to efficiently track unmarked character positions and find mirror matches.

Data Structure:

• Use a defaultdict(list) named d where:
  • Key: a character
  • Value: list of indices where this character appears and is still unmarked

Algorithm Steps:

1. Initialize variables:

   • Create an empty hash table d to store character positions
   • Set ans = 0 to accumulate the total score

2. Process each character from left to right: For each position i with character x:

   a. Calculate the mirror character:

   • Use the formula y = chr(ord('a') + ord('z') - ord(x))
   • This converts 'a' ↔ 'z', 'b' ↔ 'y', etc.

   b. Check if mirror character has unmarked positions:

   • If d[y] is not empty (mirror character y has unmarked positions):
     • Pop the last element j from d[y] using d[y].pop()
     • This gives us the closest (rightmost) unmarked position of the mirror
     • Add i - j to the answer
     • Both positions i and j are now implicitly marked (removed from tracking)
   • If d[y] is empty (no unmarked mirror positions available):
     • Append current position i to d[x] using d[x].append(i)
     • This position might be matched with a future occurrence of its mirror

3. Return the total score accumulated in ans

Why this works:

• By using pop() on the list, we always get the most recent (closest) unmarked position
• By storing positions only when no match is found, we avoid redundant storage
• Each position is handled at most twice: once when stored, once when matched and removed
• The implicit marking happens through removal from the hash table, eliminating the need for a separate "marked" array

Time Complexity: O(n) where n is the length of the string, as each character is processed once Space Complexity: O(n) in the worst case when no characters can be paired

Example Walkthrough

Let's trace through the string "dcbaz" to see how the solution works:

Initial Setup:

• d = {} (empty hash table)
• ans = 0

Step 1: Process index 0, character 'd'

• Mirror of 'd' is 'w' (using formula: chr(ord('a') + ord('z') - ord('d')) = chr(97 + 122 - 100) = chr(119) = 'w')
• Check d['w']: empty list (no unmarked 'w' positions)
• No match found, so store this position: d['d'] = [0]
• Current state: d = {'d': [0]}, ans = 0

Step 2: Process index 1, character 'c'

• Mirror of 'c' is 'x'
• Check d['x']: empty list
• No match found, so store: d['c'] = [1]
• Current state: d = {'d': [0], 'c': [1]}, ans = 0

Step 3: Process index 2, character 'b'

• Mirror of 'b' is 'y'
• Check d['y']: empty list
• No match found, so store: d['b'] = [2]
• Current state: d = {'d': [0], 'c': [1], 'b': [2]}, ans = 0

Step 4: Process index 3, character 'a'

• Mirror of 'a' is 'z'
• Check d['z']: empty list
• No match found, so store: d['a'] = [3]
• Current state: d = {'d': [0], 'c': [1], 'b': [2], 'a': [3]}, ans = 0

Step 5: Process index 4, character 'z'

• Mirror of 'z' is 'a'
• Check d['a']: contains [3]
• Match found! Pop the last (and only) element: j = 3
• Add to score: ans += 4 - 3 = 1
• After popping, d['a'] becomes empty
• Current state: d = {'d': [0], 'c': [1], 'b': [2], 'a': []}, ans = 1

Final Result: ans = 1

The only pair formed was between 'a' at index 3 and 'z' at index 4, contributing a score of 1 to the total.

Solution Implementation

Time and Space Complexity

Time Complexity: O(n)

The algorithm iterates through the string once using a single for loop that processes each character at index i. For each character:

• Computing the mirror character y using chr(ord("a") + ord("z") - ord(x)) takes O(1) time
• Checking if d[y] exists takes O(1) time (dictionary lookup)
• Either popping from the list (d[y].pop()) or appending to the list (d[x].append(i)) takes O(1) amortized time
• The arithmetic operation i - j takes O(1) time

Since we perform O(1) operations for each of the n characters, the total time complexity is O(n).

Space Complexity: O(n)

The space is primarily used by the dictionary d which stores lists of indices:

• In the worst case, when no matching pairs are found (e.g., all characters are the same), the dictionary would store all n indices
• The dictionary has at most 26 keys (one for each letter), but the total number of indices stored across all lists can be up to n
• Additional variables like ans, i, x, y, and j use O(1) space

Therefore, the space complexity is O(n) where n is the length of the string s.

Learn more about how to find time and space complexity quickly.

Common Pitfalls

Pitfall 1: Incorrect Mirror Character Calculation

The Problem: A common mistake is incorrectly calculating the mirror character. Developers might try formulas like:

• mirror = 'z' - current_char + 'a' (wrong order)
• mirror = chr(25 - (ord(current_char) - ord('a')) + ord('a')) (overcomplicated but could work)
• mirror = chr(ord('z') - ord(current_char)) (missing the 'a' offset)

Why It Happens: The mirror relationship requires mapping the first letter to the last, second to second-last, etc. The correct formula chr(ord('a') + ord('z') - ord(current_char)) works because:

• For 'a': ord('a') + ord('z') - ord('a') = ord('z')
• For 'z': ord('a') + ord('z') - ord('z') = ord('a')

Solution: Always verify the mirror calculation with test cases:

def get_mirror(char):
    return chr(ord('a') + ord('z') - ord(char))

# Test the formula
assert get_mirror('a') == 'z'
assert get_mirror('b') == 'y'
assert get_mirror('z') == 'a'
assert get_mirror('m') == 'n'

Pitfall 2: Using the Wrong End of the List

The Problem: Using char_indices[mirror_char].pop(0) instead of char_indices[mirror_char].pop() would give us the leftmost (farthest) unmarked position instead of the rightmost (closest) one.

Why It Happens: The problem explicitly states we need the "closest unmarked index j where j < i". Since we're processing left to right and storing indices in order, the last element in the list is the closest one to our current position.

Solution: Always use pop() without arguments (or pop(-1)) to get the most recent/closest index:

# Correct: gets the closest (rightmost) unmarked position
mirror_index = char_indices[mirror_char].pop()

# Wrong: gets the farthest (leftmost) unmarked position
# mirror_index = char_indices[mirror_char].pop(0)  # Don't do this!

Pitfall 3: Attempting to Track Already Matched Characters

The Problem: Some might try to add extra logic to track which indices have been "marked" or paired:

# Unnecessary complexity
marked = set()
for i, char in enumerate(s):
    if i in marked:
        continue
    # ... rest of logic

Why It Happens: The problem statement mentions "marking" indices, which might lead to overthinking the implementation.

Solution: The beauty of this approach is that "marking" happens implicitly through removal from the dictionary. Once a character index is popped from the list, it's effectively marked as used. No additional tracking is needed.