What exactly is the mirror score of a string?

The mirror score is the total number of letter pairs in the string where each letter matches the alphabetic mirror of another unmarked letter.

How do stacks help in computing mirror score?

Stacks maintain the positions of unmatched letters, enabling O(1) pairing checks with incoming characters instead of scanning the string repeatedly.

Can this approach handle very long strings efficiently?

Yes, because the algorithm iterates through the string once and uses a fixed number of stacks, ensuring linear time and constant extra space.

What should I watch out for when mapping letters to mirrors?

Ensure the mapping correctly pairs 'a' with 'z', 'b' with 'y', etc., and consistently uses lowercase letters for indexing stacks.

Is the stack-based state management pattern always needed for mirror score problems?

For this problem, it is essential to efficiently track unmatched letters and pair mirrors without scanning the entire string repeatedly.

#3412

Medium

auto_awesome栈·状态

LeetCode 题解工作台

计算字符串的镜像分数

给你一个字符串 s 。英文字母中每个字母的镜像定义为反转字母表之后对应位置上的字母。例如， 'a' 的镜像是 'z' ， 'y' 的镜像是 'b' 。最初，字符串 s 中的所有字符都未标记。字符串 s 的初始分数为 0 ，你需要对其执行以下过程：从左到右遍历字符串。对于每个下标 i…

哈希表字符串栈模拟

题目描述

给你一个字符串 s。

英文字母中每个字母的镜像定义为反转字母表之后对应位置上的字母。例如，'a' 的镜像是 'z'，'y' 的镜像是 'b'。

最初，字符串 s 中的所有字符都 未标记 。

字符串 s 的初始分数为 0 ，你需要对其执行以下过程：

从左到右遍历字符串。
对于每个下标 i ，找到距离最近的 未标记 下标 j，下标 j 需要满足 j < i 且 s[j] 是 s[i] 的镜像。然后标记下标 i 和 j，总分加上 i - j 的值。
如果对于下标 i，不存在满足条件的下标 j，则跳过该下标，继续处理下一个下标，不需要进行标记。

返回最终的总分。

示例 1：

输入： s = "aczzx"

输出： 5

解释：

i = 0。没有符合条件的下标 j，跳过。
i = 1。没有符合条件的下标 j，跳过。
i = 2。距离最近的符合条件的下标是 j = 0，因此标记下标 0 和 2，然后将总分加上 2 - 0 = 2 。
i = 3。没有符合条件的下标 j，跳过。
i = 4。距离最近的符合条件的下标是 j = 1，因此标记下标 1 和 4，然后将总分加上 4 - 1 = 3 。

示例 2：

输入： s = "abcdef"

输出： 0

解释：

对于每个下标 i，都不存在满足条件的下标 j。

提示：

1 <= s.length <= 10⁵
s 仅由小写英文字母组成。

lightbulb

解题思路

方法一：哈希表

我们可以用一个哈希表 $\textit{d}$ 来存储每个未标记的字符的下标列表，其中键是字符，值是下标列表。

我们遍历字符串 $\textit{s}$ ，对于每个字符 $\textit{x}$ ，我们找到其镜像字符 $\textit{y}$ ，如果 $\textit{d}$ 中存在 $\textit{y}$ ，我们就取出 $\textit{y}$ 对应的下标列表 $\textit{ls}$ ，取出 $\textit{ls}$ 的最后一个元素 $\textit{j}$ ，并将 $\textit{j}$ 从 $\textit{ls}$ 中移除。如果 $\textit{ls}$ 变为空，我们就将 $\textit{y}$ 从 $\textit{d}$ 中移除。此时，我们就找到了一个满足条件的下标对 $(\textit{j}, \textit{i})$ ，并将 $\textit{i} - \textit{j}$ 加到答案中。否则，我们将 $\textit{x}$ 加入到 $\textit{d}$ 中。

时间复杂度 $O(n)$ ，空间复杂度 $O(n)$ 。其中 $n$ 为字符串 $\textit{s}$ 的长度。

1

2

3

4

5

6

7

8

9

10

11

12

13

class Solution:
    def calculateScore(self, s: str) -> int:
        d = defaultdict(list)
        ans = 0
        for i, x in enumerate(s):
            y = chr(ord("a") + ord("z") - ord(x))
            if d[y]:
                j = d[y].pop()
                ans += i - j
            else:
                d[x].append(i)
        return ans

speed

复杂度分析

指标	值
时间	complexity is O(n) for n = s.length due to the single-pass iteration and constant-time stack operations. Space complexity is O(1) relative to input size because only 26 stacks for lowercase letters are maintained.
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Focus on the stack-based state management pattern for mirror matching.
question_mark
Ask about handling unmarked letters and simultaneous updates to stacks.
question_mark
Probe edge cases with repeated letters or no mirror pairs.

warning

常见陷阱

外企场景

error
Failing to map letters correctly to their mirror equivalents.
error
Forgetting to check the corresponding mirror stack before pushing the current character.
error
Using nested loops instead of stacks, leading to O(n^2) performance.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Compute mirror scores with uppercase and lowercase letters combined.
arrow_right_alt
Modify the problem to allow partial mirror pairs with a tolerance of one mismatch.
arrow_right_alt
Calculate maximum mirror score after deleting at most k characters from s.

help

常见问题

外企场景

继续练习

#3522 执行指令后的得分 #3561 移除相邻字符 #3597 分割字符串