Find Mirror Score of a String | Leetcode Problem | Complete CPP Solution

Find Mirror Score of a String | Leetcode Problem | Complete CPP Solution | C++

In this blog post, we will dive deep into solving the LeetCode problem: Find Mirror Score of a String. This is a medium difficulty problem that involves manipulating strings and understanding character relationships, specifically how they "mirror" each other in the alphabet.

We will break down the problem, explain how to approach it step-by-step, and then provide a clean and efficient solution in C++. By the end, you should have a good understanding of the problem and the optimal way to solve it.

Problem Statement

You are given a string s. We define the mirror of a letter in the English alphabet as its corresponding letter when the alphabet is reversed. For example:

The mirror of 'a' is 'z'
The mirror of 'b' is 'y'
The mirror of 'c' is 'x'
... and so on.

Your task is to calculate a mirror score of the string by following these steps:

Iterate through the string from left to right.
For each index i, find the closest unmarked index j such that j < i and s[j] is the mirror of s[i].
If such a pair (i, j) is found, mark both indices i and j and add the difference i - j to the score.
If no such pair exists, move to the next index without making any changes.
Finally, return the total score after processing the entire string.

Example Walkthrough

Example 1:

Input: s = "aczzx"

Output: 5

Explanation:

At i = 0, no matching mirror character exists to the left.
At i = 1, no matching mirror character exists to the left.
At i = 2, the closest unmarked character to the left is s[0] = 'a', which is the mirror of s[2] = 'z'. We mark both indices and add 2 - 0 = 2 to the score.
At i = 3, no matching mirror character exists to the left.
At i = 4, the closest unmarked character to the left is s[1] = 'c', which is the mirror of s[4] = 'x'. We mark both indices and add 4 - 1 = 3 to the score.

Thus, the final score is 2 + 3 = 5.

Example 2:

Input: s = "abcdef"

Output: 0

Explanation:

In this case, no pairs of characters match the mirror condition. Therefore, the total score remains 0.

Problem Constraints

1 <= s.length <= 10^5
The string s consists only of lowercase English letters.

These constraints imply that we need an efficient solution with a time complexity of $O(n)$ or $O(n \log n)$ , where $n$ is the length of the string. We must ensure our solution scales well with larger inputs.

Solution Approach

To solve this problem efficiently, we need to track pairs of mirror characters as we iterate through the string. Here’s a breakdown of the approach:

Mirror Calculation: For each character ch, its mirror is calculated as:
$\text{mirror(ch)} = 'z' - (ch - 'a')$
This formula ensures that 'a' maps to 'z', 'b' maps to 'y', and so on.
Track Indices: We need to find pairs of characters such that s[i] and s[j] are mirrors of each other. To do this efficiently, we maintain a map (charIndices) that stores the indices of characters we've seen so far. For each character at index i, we check if its mirror exists in the map. If it does, we calculate the score as i - j, mark both indices, and move on.
Efficiency Considerations: By using a hash map to store indices and a boolean array to track marked indices, we avoid nested loops that would result in a time complexity of $O(n^2)$ . Instead, we achieve a time complexity of $O(n)$ .

C++ Code Implementation

Here's the efficient solution in C++ for finding the mirror score of a string:

#include <vector>
#include <unordered_map>
#include <string>
using namespace std;

class Solution
{
public:
    char getMirrorChar(char ch)
    {
        return 'z' - (ch - 'a');
    }

    long long calculateScore(string s)
    {
        int n = s.size();
        vector<bool> isMarked(n, false);
        unordered_map<char, vector<int>> charIndices;
        long long score = 0;

        for (int i = 0; i < n; ++i)
        {
            char mirrorChar = getMirrorChar(s[i]);
            if (charIndices[mirrorChar].empty())
            {
                charIndices[s[i]].push_back(i);
            }
            else
            {
                int j = charIndices[mirrorChar].back();
                charIndices[mirrorChar].pop_back();
                isMarked[i] = true;
                isMarked[j] = true;
                score += i - j;
            }
        }

        return score;
    }
};

Key Points of the Code

getMirrorChar: This function calculates the mirror character for a given character ch by using the formula mirror(ch) = 'z' - (ch - 'a').
calculateScore: This is the main function where we iterate over the string, calculate mirrors, and compute the total score based on valid pairs of mirror characters.

Time Complexity

Time Complexity: $O(n)$ , where $n$ is the length of the string. We iterate through the string once and perform constant-time operations (hash map lookups and updates).
Space Complexity: $O(n)$ , due to the space required for the charIndices map and the isMarked vector.

AlgoPush

Search This Blog