comments	difficulty	edit_url
true	中等	https://github.com/doocs/leetcode/edit/main/solution/3400-3499/3412.Find%20Mirror%20Score%20of%20a%20String/README.md

3412. 计算字符串的镜像分数

English Version

题目描述

给你一个字符串 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 <= 105
• s 仅由小写英文字母组成。

解法

方法一：哈希表

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

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

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

Python3

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

Java

class Solution {
    public long calculateScore(String s) {
        Map<Character, List<Integer>> d = new HashMap<>(26);
        int n = s.length();
        long ans = 0;
        for (int i = 0; i < n; ++i) {
            char x = s.charAt(i);
            char y = (char) ('a' + 'z' - x);
            if (d.containsKey(y)) {
                var ls = d.get(y);
                int j = ls.remove(ls.size() - 1);
                if (ls.isEmpty()) {
                    d.remove(y);
                }
                ans += i - j;
            } else {
                d.computeIfAbsent(x, k -> new ArrayList<>()).add(i);
            }
        }
        return ans;
    }
}

C++

class Solution {
public:
    long long calculateScore(string s) {
        unordered_map<char, vector<int>> d;
        int n = s.length();
        long long ans = 0;
        for (int i = 0; i < n; ++i) {
            char x = s[i];
            char y = 'a' + 'z' - x;
            if (d.contains(y)) {
                vector<int>& ls = d[y];
                int j = ls.back();
                ls.pop_back();
                if (ls.empty()) {
                    d.erase(y);
                }
                ans += i - j;
            } else {
                d[x].push_back(i);
            }
        }
        return ans;
    }
};

Go

func calculateScore(s string) (ans int64) {
	d := make(map[rune][]int)
	for i, x := range s {
		y := 'a' + 'z' - x
		if ls, ok := d[y]; ok {
			j := ls[len(ls)-1]
			d[y] = ls[:len(ls)-1]
			if len(d[y]) == 0 {
				delete(d, y)
			}
			ans += int64(i - j)
		} else {
			d[x] = append(d[x], i)
		}
	}
	return
}

TypeScript

function calculateScore(s: string): number {
    const d: Map<string, number[]> = new Map();
    const n = s.length;
    let ans = 0;
    for (let i = 0; i < n; i++) {
        const x = s[i];
        const y = String.fromCharCode('a'.charCodeAt(0) + 'z'.charCodeAt(0) - x.charCodeAt(0));

        if (d.has(y)) {
            const ls = d.get(y)!;
            const j = ls.pop()!;
            if (ls.length === 0) {
                d.delete(y);
            }
            ans += i - j;
        } else {
            if (!d.has(x)) {
                d.set(x, []);
            }
            d.get(x)!.push(i);
        }
    }
    return ans;
}