3412. Find Mirror Score of a String LeetCode Solution

In this guide, you will get 3412. Find Mirror Score of a String LeetCode Solution with the best time and space complexity. The solution to Find Mirror Score of a String problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.

Problem Statement
Complexity Analysis
Find Mirror Score of a String solution in C++
Find Mirror Score of a String solution in Java
Find Mirror Score of a String solution in Python
Additional Resources

3412. Find Mirror Score of a String LeetCode Solution image

Problem Statement of Find Mirror Score of a String

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’, and the mirror of ‘y’ is ‘b’.
Initially, all characters in the string s are unmarked.
You start with a score of 0, and you perform the following process on the string s:

Iterate through the string from left to right.
At each index i, find the closest unmarked index j such that j < i and s[j] is the mirror of s[i]. Then, mark both indices i and j, and add the value i – j to the total score.
If no such index j exists for the index i, move on to the next index without making any changes.

Return the total score at the end of the process.

Example 1:

Input: s = “aczzx”
Output: 5
Explanation:

i = 0. There is no index j that satisfies the conditions, so we skip.
i = 1. There is no index j that satisfies the conditions, so we skip.
i = 2. The closest index j that satisfies the conditions is j = 0, so we mark both indices 0 and 2, and then add 2 – 0 = 2 to the score.
i = 3. There is no index j that satisfies the conditions, so we skip.
i = 4. The closest index j that satisfies the conditions is j = 1, so we mark both indices 1 and 4, and then add 4 – 1 = 3 to the score.

Example 2:

Input: s = “abcdef”
Output: 0
Explanation:
For each index i, there is no index j that satisfies the conditions.

Constraints:

1 <= s.length <= 105
s consists only of lowercase English letters.

Complexity Analysis

Time Complexity: O(n)
Space Complexity: O(n)

3412. Find Mirror Score of a String LeetCode Solution in C++

class Solution {
 public:
  long long calculateScore(string s) {
    long ans = 0;
    vector<stack<int>> indices(26);

    for (int i = 0; i < s.length(); ++i) {
      const int index = s[i] - 'a';
      const int oppositeIndex = 25 - index;
      if (!indices[oppositeIndex].empty())
        ans += i - indices[oppositeIndex].top(), indices[oppositeIndex].pop();
      else
        indices[index].push(i);
    }

    return ans;
  }
};
/* code provided by PROGIEZ */

3412. Find Mirror Score of a String LeetCode Solution in Java

class Solution {
  public long calculateScore(String s) {
    long ans = 0;
    Deque<Integer>[] indices = new ArrayDeque[26];

    for (int i = 0; i < 26; ++i)
      indices[i] = new ArrayDeque<>();

    for (int i = 0; i < s.length(); ++i) {
      final int index = s.charAt(i) - 'a';
      final int oppositeIndex = 25 - index;
      if (!indices[oppositeIndex].isEmpty())
        ans += i - indices[oppositeIndex].poll();
      else
        indices[index].push(i);
    }

    return ans;
  }
}
// code provided by PROGIEZ

3412. Find Mirror Score of a String LeetCode Solution in Python

class Solution:
  def calculateScore(self, s: str) -> int:
    ans = 0
    indices = [[] for _ in range(26)]

    for i, c in enumerate(s):
      index = ord(c) - ord('a')
      oppositeIndex = 25 - index
      if indices[oppositeIndex]:
        ans += i - indices[oppositeIndex].pop()
      else:
        indices[index].append(i)

    return ans
 # code by PROGIEZ