跳转至

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

题目描述

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

解法

方法一：哈希表

我们可以用一个哈希表 $\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
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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
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;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
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;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
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
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
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;
}

评论