HashMap典型题-最美字符串的数目

发表于 分类于 ， Valine：

前段时间总结过一篇介绍通过 HashMap 提升查找效率的文章，实际上，这类问题代码通常并不复杂，难点常常是设计 HashMap 的 key 值上。leetcode 247场周赛的一道题目 1915. 最美子字符串的数目 就是一个典型的需要使用一些技巧来设计 HashMap 的 key 的问题。

1. 题目

如果某个字符串中 至多一个 字母出现 奇数 次，则称其为 最美 字符串。

例如，”ccjjc” 和 “abab” 都是最美字符串，但 “ab” 不是。
给你一个字符串 word ，该字符串由前十个小写英文字母组成（’a’ 到 ‘j’）。请你返回 word 中 最美非空子字符串 的数目。如果同样的子字符串在 word 中出现多次，那么应当对 每次出现 分别计数。

子字符串 是字符串中的一个连续字符序列。

题中数据规模：1 <= word.length <= 1e5

2. 分析

根据经验，通常 数据规模在 1e5 时，O(n^2) 的解法一定是超过时间限制的。因此，暴力解法直接不用考虑。而题目中所谓的最美子字符串，也是一种具有一定特点的子字符串，而子字符串问题，常常可以通过保存 “前缀和” 进行处理。 具体的，在遍历字符串的同时，保存前缀和，然后根据 “子字符串 = 前缀和的差值” 这一关系，根据当前遍历到的前缀和的情况和 要求的 子字符串的特点，得到目标前缀和，然后找到对应的前缀和出现的次数，从而快速的进行求解。

而这里的困难点是如何 表示 前缀和。由于题目要求的是 字符串中出现字符的奇偶性具有一定特点，而我们知道 奇偶性实际上是一个 二元的特征量（即 只有两种可能，非 奇 即 偶），又题目中给定我们条件，字符串中只会出现 ‘a’ - ‘j’ 这 10 个字符之间的字符， 因此我们想到可以使用 一个 10 位的二进制的数来 保存 前缀中奇偶性的特征，作为我们前缀和 的 key 值，value 值则是截止当前遍历到的字符，相应的 前缀和出现的次数。使用一个这样的整数作为 key 值，是非常方便的， 首先我们不需要重写 equals() 方法和 hashCode() 方法， 其次，我们可以通过 位 操作，高效的修改 前缀 key 值的信息。

具体地，我们的 key 值设计如下图所示：

key 值最大为 2^10 - 1。每次增加一个字符时，我们只需要找到该字符对应的位，然后将前面的 prefixInfo 与 对应位为1的值进行异或操作，就可以改变对应位上的奇偶性信息。

搜索时，由于题目中要求最多有一个字母出现奇数次，也就是说区间左边界和右边界对应的两个前缀最多有 一个字母奇偶性信息不同，也就是说二进制 表示的 key 上最多有一个位不同。因此，我们可以遍历寻找最低位不同、次低位不同、第三低位不同、… 的情况，找到所有满足的前缀和。具体的，可以通过 与 0x1, 0x10, 0x100 … 异或来快速的寻找满足要求的 key 值。具体代码实现如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
    public long wonderfulSubstrings(String word) {
        int prefixInfo = 0;
        long res = 0;
        // map 记录已经遍历的前缀的情况
        Map<Integer, Integer> map = new HashMap<>();
        // 边界情况，没有任何字符时，相当于所有位都是偶数，出现 1 次
        map.put(0, 1);
        for(int i = 0; i < word.length(); ++i){
            // 添加一个字符，更新前缀信息
            int x = word.charAt(i) - 'a';
            prefixInfo = prefixInfo ^ (1 << x);

            // 没有字母出现偶数次的情况
            res += map.getOrDefault(prefixInfo, 0);
            // 分析每个字母出现次数为奇数的情况
            for(int j = 0; j < 10; ++j){
                int key = (1<<j) ^ prefixInfo;
                res += map.getOrDefault(key, 0);
            }
            // 添加当前前缀和信息到 map 中
            map.put(prefixInfo, map.getOrDefault(prefixInfo, 0) + 1);
        }
        return res;
    }
}

由于 key 值最大就是 1024（2^10），是一个确定的范围，因此可以使用 一个 int[] 数组来存放 前缀和 信息，具体的，数组的位号作为 key 值，数组中的值为 value，表示对应位号 表示的 前缀和出现的次数，修改后的代码如下（leetcode 测试中下面的代码执行时间更短）：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
    public long wonderfulSubstrings(String word) {
        int prefixInfo = 0;
        long res = 0;
        int[] map = new int[1024];
        map[0] = 1;
        for(int i = 0; i < word.length(); ++i){
            int x = word.charAt(i) - 'a';
            prefixInfo = prefixInfo ^ (1 << x);
            res += map[prefixInfo];
            for(int j = 0; j < 10; ++j){
                int key = (1 << j) ^ prefixInfo;
                res += map[key];
            }
            map[prefixInfo] += 1;
        }
        return res;
    }
}