最美字符串的数目

5799. 最美子字符串的数目

难度中等8

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

• 例如，"ccjjc" 和 "abab" 都是最美字符串，但 "ab" 不是。

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

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

示例 1：

输入：word = "aba"
输出：4
解释：4 个最美子字符串如下所示：
- "aba" -> "a"
- "aba" -> "b"
- "aba" -> "a"
- "aba" -> "aba"

示例 2：

输入：word = "aabb"
输出：9
解释：9 个最美子字符串如下所示：
- "aabb" -> "a"
- "aabb" -> "aa"
- "aabb" -> "aab"
- "aabb" -> "aabb"
- "aabb" -> "a"
- "aabb" -> "abb"
- "aabb" -> "b"
- "aabb" -> "bb"
- "aabb" -> "b"

示例 3：

输入：word = "he"
输出：2
解释：2 个最美子字符串如下所示：
- "he" -> "h"
- "he" -> "e"

提示：

• 1 <= word.length <= 105
• word 由从 'a' 到 'j' 的小写英文字母组成

通过次数600

提交次数3,349

状态压缩

class Solution {
    public long wonderfulSubstrings(String word) {
        char[] chars = word.toCharArray();
        int len = chars.length;
        Map<Integer, Integer> mm = new HashMap<>();
        long res = 0;
        mm.put(0, 1);
        int state = 0;
        for (int i = 0; i < len; i++) {
            state = nextState(state, chars[i]);
            res += mm.getOrDefault(state, 0);
            for (int j = 0; j < 10; j++) {
                int tmp = state;
                tmp = nextState(tmp, (char)(j + 'a'));
                res += mm.getOrDefault(tmp, 0);
            }
            mm.put(state, mm.getOrDefault(state, 0) + 1);
        }
        return res;
    }
    public int nextState(int state, char c) {
        int m = c - 'a';
        state = (state ^ (1 << m));
        return state;
    }
    public int getOnes(int state) {
        int res = 0;
        while (state != 0) {
            state = (state) & (state - 1);
            res++;
        }
        return res;
    }
}

作者：puck1609
链接：https://leetcode-cn.com/problems/number-of-wonderful-substrings/solution/javashuang-bai-zhuang-tai-ya-suo-by-puck-eo0r/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

赏

谢谢你请我吃糖果

微信