Medium

题目描述

给你一个字符串 s。

如果可以将字符串 s 分割成两个非空字符串 sleft 和 sright，使得它们的连接等于 s（即 sleft + sright = s），并且 sleft 和 sright 中不同字母的数目相同，那么这种分割就被称为「好分割」。

返回 s 中好分割的数目。

示例 1：

输入：s = "aacaba"
输出：2
解释：共有 5 种分割 "aacaba" 的方法，其中 2 种是好分割。
("a", "acaba") 左字符串和右字符串分别包含 1 个和 3 个不同的字母。
("aa", "caba") 左字符串和右字符串分别包含 1 个和 3 个不同的字母。
("aac", "aba") 左字符串和右字符串分别包含 2 个和 2 个不同的字母（好分割）。
("aaca", "ba") 左字符串和右字符串分别包含 2 个和 2 个不同的字母（好分割）。
("aacab", "a") 左字符串和右字符串分别包含 3 个和 1 个不同的字母。

示例 2：

输入：s = "abcd"
输出：1
解释：按如下方式分割字符串 ("ab", "cd")。

提示：

  • 1 <= s.length <= 10^5
  • s 仅由小写英文字母组成。

解题思路

这道题要求统计字符串的好分割数目，即左右两部分不同字符数量相等的分割点。

核心思路是对每个可能的分割位置，分别计算左右两部分的不同字符数量。有两种主要解法：

解法一：双指针+哈希表 遍历每个分割点，使用两个哈希表分别统计左右部分的字符出现次数，然后比较不同字符的数量。时间复杂度 O(n²)。

解法二：预处理优化（推荐） 先预处理计算出每个位置右侧的不同字符数量，然后一次遍历，动态维护左侧的不同字符数量。具体步骤：

  1. 从右向左遍历，计算每个位置右侧（包含当前位置）的不同字符数量
  2. 从左向右遍历每个分割点，动态维护左侧不同字符数量，并与预处理的右侧数量比较

这种方法只需要遍历两次字符串，时间复杂度优化到 O(n)，空间复杂度 O(1)（仅使用固定大小的字符计数数组）。

代码实现

class Solution {
public:
    int numSplits(string s) {
        int n = s.length();
        vector<int> rightDistinct(n, 0);
        vector<int> charCount(26, 0);
        
        // 从右向左计算每个位置右侧的不同字符数
        int distinct = 0;
        for (int i = n - 1; i >= 0; i--) {
            if (charCount[s[i] - 'a'] == 0) {
                distinct++;
            }
            charCount[s[i] - 'a']++;
            rightDistinct[i] = distinct;
        }
        
        // 从左向右遍历，计算左侧不同字符数并比较
        fill(charCount.begin(), charCount.end(), 0);
        int leftDistinct = 0;
        int result = 0;
        
        for (int i = 0; i < n - 1; i++) {
            if (charCount[s[i] - 'a'] == 0) {
                leftDistinct++;
            }
            charCount[s[i] - 'a']++;
            
            if (leftDistinct == rightDistinct[i + 1]) {
                result++;
            }
        }
        
        return result;
    }
};

class Solution:
    def numSplits(self, s: str) -> int:
        n = len(s)
        right_distinct = [0] * n
        char_count = [0] * 26
        
        # 从右向左计算每个位置右侧的不同字符数
        distinct = 0
        for i in range(n - 1, -1, -1):
            if char_count[ord(s[i]) - ord('a')] == 0:
                distinct += 1
            char_count[ord(s[i]) - ord('a')] += 1
            right_distinct[i] = distinct
        
        # 从左向右遍历，计算左侧不同字符数并比较
        char_count = [0] * 26
        left_distinct = 0
        result = 0
        
        for i in range(n - 1):
            if char_count[ord(s[i]) - ord('a')] == 0:
                left_distinct += 1
            char_count[ord(s[i]) - ord('a')] += 1
            
            if left_distinct == right_distinct[i + 1]:
                result += 1
        
        return result

public class Solution {
    public int NumSplits(string s) {
        int n = s.Length;
        int[] rightDistinct = new int[n];
        int[] charCount = new int[26];
        
        // 从右向左计算每个位置右侧的不同字符数
        int distinct = 0;
        for (int i = n - 1; i >= 0; i--) {
            if (charCount[s[i] - 'a'] == 0) {
                distinct++;
            }
            charCount[s[i] - 'a']++;
            rightDistinct[i] = distinct;
        }
        
        // 从左向右遍历，计算左侧不同字符数并比较
        Array.Fill(charCount, 0);
        int leftDistinct = 0;
        int result = 0;
        
        for (int i = 0; i < n - 1; i++) {
            if (charCount[s[i] - 'a'] == 0) {
                leftDistinct++;
            }
            charCount[s[i] - 'a']++;
            
            if (leftDistinct == rightDistinct[i + 1]) {
                result++;
            }
        }
        
        return result;
    }
}

var numSplits = function(s) {
    const n = s.length;
    const rightDistinct = new Array(n).fill(0);
    let charCount = new Array(26).fill(0);
    
    // 从右向左计算每个位置右侧的不同字符数
    let distinct = 0;
    for (let i = n - 1; i >= 0; i--) {
        const charIndex = s.charCodeAt(i) - 97; // 'a'.charCodeAt(0) = 97
        if (charCount[charIndex]
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型值
时间复杂度O(n)
空间复杂度O(n)

其中 n 为字符串长度。时间复杂度为 O(n) 是因为只需要遍历字符串两次。空间复杂度为 O(n) 主要用于存储每个位置右侧的不同字符数量数组，字符计数数组大小固定为 26。