3412. Find Mirror Score of a String

MediumStackHash TableStringSimulation

Problem Description

Given a string s, you need to calculate a score based on a specific procedure. The procedure involves the concept of a "mirror" letter in the English alphabet, which is defined as the 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 iterate through the string from left to right, aiming to find pairs of characters where one character is the mirror of another. For each character at index i, find the closest unmarked index j such that j < i and s[j] is the mirror of s[i]. If such an index is found, mark both i and j and add the value i - j to the total score. If no such index exists, simply move to the next character. Continue this process until you have processed the entire string and return the total score.

Intuition

To solve this problem, we use a hash table (dictionary) to efficiently keep track of indices of unmarked characters. The key insight is to store indices of each character in the string so that when we identify a character, we can quickly check if its mirror is present among previously unmarked indices.

Use of Hash Table: By using a hash table (d), we can map each character to a list of indices where the character appears, and that still need potential pairing. The idea is to keep these indices in a list such that we can pop the last added index if a pairing happens.
Iterative Character Processing: As we iterate over each character x at index i, we determine its mirror character y by using the relation: y = chr(ord('a') + ord('z') - ord(x)). This helps to efficiently calculate the mirrored character.
Pairing and Scoring: If our hash table contains the mirror character y, we pop the last index from its list, which gives the closest possible unmarked mirror index j that is less than i. By marking both index i and j, and calculating the score increment as i - j, we ensure maximized score contribution and efficient marking.
Handling Unpaired Characters: If no mirror character y is found for x, we add the current index i to the list of indices for x in the hash table, effectively marking it for potential future pairings.

This systematic approach ensures that all potential mirror pairings are covered while optimizing the scoring through smart index tracking and dynamic list handling in the hash table.

Learn more about Stack patterns.

Solution Approach

To implement the solution, we use a hash table (or dictionary) to facilitate efficient lookups and store indices of unmarked characters:

Data Structures Used:
- A hash table d where each key is a character and the associated value is a list of indices where this character appears in the string and hasn't been paired yet.
Algorithm Steps:
- Initialize d as a defaultdict with lists to store indices for each character, and a variable ans to accumulate the score.
- Traverse the string s using a loop, where i is the current index and x is the current character.
- Compute the mirror character y for x using the formula: y = chr(ord('a') + ord('z') - ord(x)).
- Check if there exists any unmarked index for the mirror character y in hash table d:
  - If yes, extract this index j using j = d[y].pop() and add the difference i - j to the score ans.
  - If no, append the current index i to the list of indices for character x in d.
- This ensures if a mirror character for x appears later, we can efficiently find it and score the difference.
- Finally, return the accumulated score ans.

By using a stack-like structure for each character's unmarked indices in the hash table d, we efficiently track and pair characters, ensuring optimal scoring while avoiding unnecessary re-iteration.

Ready to land your dream job?

Unlock your dream job with a 2-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Consider the example string s = "abzyc". We'll calculate the score based on the procedure described:

Initial Setup:
- Initialize a hash table d as a defaultdict of lists.
- Start with a score ans = 0.
Process Each Character:
- Index 0 ('a'):
  - Determine mirror character: y = 'z' (since z is mirror of a).
  - 'z' is not in d, so add 0 to d['a']. Now, d is {'a': [0]}.
- Index 1 ('b'):
  - Determine mirror character: y = 'y' (since y is mirror of b).
  - 'y' is not in d, so add 1 to d['b']. Now, d is {'a': [0], 'b': [1]}.
- Index 2 ('z'):
  - Determine mirror character: y = 'a' (since a is mirror of z).
  - 'a' is in d with indices [0], pop 0.
  - Increment score by 2 - 0 = 2. Score ans becomes 2.
  - d is now {'a': [], 'b': [1]}.
- Index 3 ('y'):
  - Determine mirror character: y = 'b' (since b is mirror of y).
  - 'b' is in d with indices [1], pop 1.
  - Increment score by 3 - 1 = 2. Score ans becomes 4.
  - d is now {'a': [], 'b': []}.
- Index 4 ('c'):
  - Determine mirror character: y = 'x' (since x is mirror of c).
  - 'x' is not in d, so add 4 to d['c']. Now, d is {'a': [], 'b': [], 'c': [4]}.
Final Score:
- The total accumulated score is 4.

Through this step-by-step example, we can visualize how the solution approach efficiently pairs mirror characters and calculates the score.

Solution Implementation

1from collections import defaultdict
2
3class Solution:
4    def calculateScore(self, s: str) -> int:
5        # Dictionary to store indices of characters and their complementary characters
6        d = defaultdict(list)
7        ans = 0
8      
9        for i, x in enumerate(s):
10            # Calculate the complementary character of x
11            y = chr(ord('a') + ord('z') - ord(x))
12          
13            # Check if there is a previously recorded index of the complementary character
14            if d[y]:
15                # Pop the last index of the complementary character and calculate the score
16                j = d[y].pop()
17                ans += i - j
18            else:
19                # Record the current index of the character
20                d[x].append(i)
21      
22        # Return the accumulated score
23        return ans
24

1import java.util.*;
2
3class Solution {
4    // Method to calculate score based on the given string
5    public long calculateScore(String s) {
6        // Map to track character indices, with a capacity that hints storing all lowercase letters
7        Map<Character, List<Integer>> charIndicesMap = new HashMap<>(26);
8        int length = s.length();  // Length of the input string
9        long score = 0;  // Variable to accumulate the score
10
11        // Iterate over each character in the string
12        for (int currentIndex = 0; currentIndex < length; ++currentIndex) {
13            char currentChar = s.charAt(currentIndex);  // Current character
14            char counterpartChar = (char) ('a' + 'z' - currentChar);  // Character that pairs with currentChar
15
16            // Check if the counterpart character has been encountered before
17            if (charIndicesMap.containsKey(counterpartChar)) {
18                List<Integer> indicesList = charIndicesMap.get(counterpartChar);  // Retrieve indices of counterpartChar
19                int previousIndex = indicesList.remove(indicesList.size() - 1);  // Get the most recent index of counterpartChar
20
21                // If there are no more indices for counterpartChar, remove it from the map
22                if (indicesList.isEmpty()) {
23                    charIndicesMap.remove(counterpartChar);
24                }
25              
26                // Calculate the score by adding the difference in indices
27                score += currentIndex - previousIndex;
28            } else {
29                // Add the current character and index to the map if counterpartChar doesn't exist
30                charIndicesMap.computeIfAbsent(currentChar, k -> new ArrayList<>()).add(currentIndex);
31            }
32        }
33        return score;  // Return the computed score
34    }
35}
36

1#include <unordered_map>
2#include <vector>
3#include <string>
4
5class Solution {
6public:
7    long long calculateScore(std::string s) {
8        // This unordered_map tracks the indices where each character appears.
9        std::unordered_map<char, std::vector<int>> charIndices;
10      
11        int n = s.length(); // Length of the input string.
12        long long ans = 0; // This will hold the final score.
13
14        // Iterate over each character in the string.
15        for (int i = 0; i < n; ++i) {
16            char currentChar = s[i]; // Current character under consideration.
17
18            // Calculate the 'paired' character which forms a balanced pair with currentChar.
19            char pairedChar = 'a' + 'z' - currentChar;
20
21            // Check if the paired character has appeared before.
22            if (charIndices.contains(pairedChar)) {
23                std::vector<int>& pairedIndices = charIndices[pairedChar];
24
25                // Get the index of the last occurrence of the paired character.
26                int pairedIndex = pairedIndices.back();
27                pairedIndices.pop_back(); // Remove it from the list.
28
29                // If no more indices are left for this character, remove it from the map.
30                if (pairedIndices.empty()) {
31                    charIndices.erase(pairedChar);
32                }
33
34                // Calculate the score contributed by this pair.
35                ans += i - pairedIndex;
36            } else {
37                // If no matching pair character found, store the current character index.
38                charIndices[currentChar].push_back(i);
39            }
40        }
41
42        return ans;
43    }
44};
45

1/**
2 * Calculates the score based on the given string.
3 * @param s - The input string containing lowercase letters.
4 * @returns The score as a number.
5 */
6function calculateScore(s: string): number {
7    // Map to store indices of each character for pairing
8    const indexMap: Map<string, number[]> = new Map();
9    const stringLength = s.length;
10    let score = 0;
11
12    // Iterate over each character in the string
13    for (let i = 0; i < stringLength; i++) {
14        const currentChar = s[i];
15      
16        // Find the complementary character (forming 26 pairs such as 'a' <-> 'z', 'b' <-> 'y', etc.)
17        const complementChar = String.fromCharCode(
18            'a'.charCodeAt(0) + 'z'.charCodeAt(0) - currentChar.charCodeAt(0)
19        );
20
21        // Check if the complementary character exists in the map
22        if (indexMap.has(complementChar)) {
23            const indices = indexMap.get(complementChar)!; // Retrieve and assert non-null array of indices
24            const matchedIndex = indices.pop()!; // Find the index of the matched complementary character
25
26            // Remove entry from map if the list is empty
27            if (indices.length === 0) {
28                indexMap.delete(complementChar);
29            }
30          
31            // Update score by adding the distance between the matching pair indices
32            score += i - matchedIndex;
33        } else {
34            // If the complementary character doesn't exist, add the current character index to the map
35            if (!indexMap.has(currentChar)) {
36                indexMap.set(currentChar, []);
37            }
38            indexMap.get(currentChar)!.push(i); // Store index of current character
39        }
40    }
41
42    return score;
43}
44

Time and Space Complexity

The time complexity is O(n) because the algorithm iterates over the string s once, performing constant-time operations for each character, such as dictionary access and list operations.

The space complexity is O(n) since in the worst case, every character of the string is stored in the dictionary d, resulting in space consumption proportional to the length of the string.

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

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Question 1 out of 10

How would you design a stack which has a function min that returns the minimum element in the stack, in addition to push and pop? All push, pop, min should have running time O(1).

Add another stack to store the minimums

Add a heap to store the minimums

Add a variable to track the minimum

Add a queue to store the minumums

I don’t know