We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Find Mirror Score of a String

Number: 3634

Difficulty: Medium

Paid? No

Companies: N/A

Problem Description

Given a string s consisting of lowercase English letters, pair characters that are mirrors of each other (where the mirror of a letter is defined as the corresponding letter when the alphabet is reversed, e.g., mirror of 'a' is 'z' and mirror of 'b' is 'y'). Process the string from left to right. For each index i, find the closest unmarked index j (with j < i) such that s[j] is the mirror of s[i]. Mark both indices, add (i - j) to the total score, and continue. Return the total score after processing the entire string.

Key Insights

  • The mirror of a given letter c can be computed using the formula: mirror(c) = char('z' - (c - 'a')).
  • Process the string in a single pass (left-to-right) for an O(n) time solution.
  • Use a hash table (or dictionary) to store unpaired indices for each letter. Stacks (LIFO) for each letter allow retrieving the closest unmarked index quickly.
  • When encountering a character, check if there exists an unpaired matching mirror character; if so, pop that index and add the difference to the score. Otherwise, save the current index for a potential future match.
  • Greedy pairing ensures that we always select the closest unmarked mirror index.

Space and Time Complexity

Time Complexity: O(n), where n is the length of the string
Space Complexity: O(n), to store indices in the hash table in the worst case

Solution

The solution uses a hash table where keys are characters and values are stacks (lists or similar data structures) that store indices of unpaired occurrences of that character. For each character in the string, compute its mirror. If a matching unpaired mirror exists (i.e., there is an index in the stack corresponding to the mirror letter), pop that index, calculate the distance, and add it to the total score. If not, push the current index into the stack for later matching. This greedy approach ensures pairing with the closest mirror occurrence and guarantees an optimal solution.

Code Solutions

# Python solution with line-by-line comments
from collections import defaultdict

def find_mirror_score(s: str) -> int:
    # Helper function to compute the mirror of a character.
    def mirror(char: str) -> str:
        return chr(ord("z") - (ord(char) - ord("a")))
    
    # Dictionary mapping a character to a list of unpaired indices.
    index_stacks = defaultdict(list)
    total_score = 0

    # Iterate over the string.
    for i, char in enumerate(s):
        target = mirror(char)  # Get mirror character.
        # If there is an unpaired index for the target mirror letter.
        if index_stacks[target]:
            # Pop the most recent unpaired index (closest to i).
            j = index_stacks[target].pop()
            total_score += i - j  # Add the distance to the score.
        else:
            # No available mirror index, push current index to be used later.
            index_stacks[char].append(i)
    
    return total_score

# Example usage:
# print(find_mirror_score("aczzx"))
← Back to All Questions