Medium

题目描述

如果字符串中最多只有一个字母出现奇数次，那么该字符串就是一个神奇字符串。

  • 例如，“ccjjc” 和 “abab” 是神奇字符串，但 “ab” 不是。

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

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

示例 1：

输入：word = "aba"
输出：4
解释：四个神奇字符串分别是：
- "aba" -> "a"
- "aba" -> "b"  
- "aba" -> "a"
- "aba" -> "aba"

示例 2：

输入：word = "aabb"
输出：9
解释：九个神奇字符串分别是：
- "aabb" -> "a"
- "aabb" -> "aa"
- "aabb" -> "aab"
- "aabb" -> "aabb"
- "aabb" -> "a"
- "aabb" -> "abb"
- "aabb" -> "b"
- "aabb" -> "bb"
- "aabb" -> "b"

示例 3：

输入：word = "he"
输出：2
解释：两个神奇字符串分别是：
- "he" -> "h"
- "he" -> "e"

约束条件：

  • 1 <= word.length <= 10^5
  • word 由小写英文字母 ‘a’ 到 ‘j’ 组成

解题思路

这道题的核心思想是利用位掩码和前缀异或来高效统计神奇子字符串的数量。

关键观察：

  1. 神奇字符串要求最多有一个字符出现奇数次，其余字符都出现偶数次
  2. 字符串只包含 ‘a’ 到 ‘j’ 共10个字符，可以用10位的二进制数表示每个字符的奇偶性
  3. 对于任意子字符串 word[i:j+1]，其字符奇偶性可以通过前缀异或来计算

算法思路：

  1. 使用位掩码 mask 表示当前前缀中每个字符的奇偶性（0表示偶数次，1表示奇数次）
  2. 维护一个哈希表记录每种掩码出现的次数
  3. 对于当前位置的掩码，寻找之前出现过的掩码，满足：
    • 相同掩码：对应子字符串所有字符都是偶数次（神奇）
    • 仅差1位的掩码：对应子字符串有且仅有1个字符是奇数次（神奇）

时间复杂度优化： 由于只有10个字符，我们可以遍历所有可能的单位掩码（2^0 到 2^9），而不需要生成所有可能的掩码组合。

这种方法避免了暴力枚举所有子字符串的O(n²)复杂度，将时间复杂度降低到O(n)。

代码实现

class Solution {
public:
    long long wonderfulSubstrings(string word) {
        unordered_map<int, int> count;
        count[0] = 1;  // 空前缀
        
        long long result = 0;
        int mask = 0;
        
        for (char c : word) {
            mask ^= 1 << (c - 'a');
            
            // 寻找相同掩码（所有字符偶数次）
            result += count[mask];
            
            // 寻找仅差1位的掩码（恰好1个字符奇数次）
            for (int i = 0; i < 10; i++) {
                result += count[mask ^ (1 << i)];
            }
            
            count[mask]++;
        }
        
        return result;
    }
};

class Solution:
    def wonderfulSubstrings(self, word: str) -> int:
        count = {0: 1}  # 空前缀
        result = 0
        mask = 0
        
        for c in word:
            mask ^= 1 << (ord(c) - ord('a'))
            
            # 寻找相同掩码（所有字符偶数次）
            result += count.get(mask, 0)
            
            # 寻找仅差1位的掩码（恰好1个字符奇数次）
            for i in range(10):
                result += count.get(mask ^ (1 << i), 0)
            
            count[mask] = count.get(mask, 0) + 1
        
        return result

public class Solution {
    public long WonderfulSubstrings(string word) {
        var count = new Dictionary<int, int> { {0, 1} }; // 空前缀
        long result = 0;
        int mask = 0;
        
        foreach (char c in word) {
            mask ^= 1 << (c - 'a');
            
            // 寻找相同掩码（所有字符偶数次）
            if (count.ContainsKey(mask)) {
                result += count[mask];
            }
            
            // 寻找仅差1位的掩码（恰好1个字符奇数次）
            for (int i = 0; i < 10; i++) {
                int targetMask = mask ^ (1 << i);
                if (count.ContainsKey(targetMask)) {
                    result += count[targetMask];
                }
            }
            
            if (count.ContainsKey(mask)) {
                count[mask]++;
            } else {
                count[mask] = 1;
            }
        }
        
        return result;
    }
}

var wonderfulSubstrings = function(word) {
    const count = new Map();
    count.set(0, 1); // 空前缀
    
    let result = 0;
    let mask = 0;
    
    for (const c of word) {
        mask ^= 1 << (c.charCodeAt(0) - 'a'.charCodeAt(0));
        
        // 寻找相同掩码（所有字符偶数次）
        result += count.get(mask) || 0;
        
        // 寻找仅差1位的掩码（恰好1个字符奇数次）
        for (let i = 0; i < 10; i++) {
            result += count.get(mask ^ (1 << i)) || 0;
        }
        
        count.set(mask, (count.get(mask) || 0) + 1);
    }
    
    return result;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(10n) = O(n)遍历字符串一次，每次内部循环固定10次
空间复杂度O(2^10) = O(1024)哈希表最多存储1024种不同的掩码状态