What defines a good split in this problem?

A split of s into sleft and sright is good if both sides contain the same number of distinct letters.

Can this be solved without hash maps?

Using arrays for fixed lowercase letters is possible, but hash maps generalize better for dynamic state transition tracking.

What is the key pattern used in this problem?

The problem uses a state transition dynamic programming pattern to maintain and compare distinct letter counts efficiently.

How to handle very long strings efficiently?

Incrementally update leftCount and rightCount while iterating to ensure O(n) time instead of recomputing distinct letters repeatedly.

What common mistakes should I avoid?

Avoid recomputing distinct counts at every split and remember to remove characters from the right hash map when their count reaches zero.

#1525

Medium

auto_awesome状态·转移·动态规划

LeetCode 题解工作台

字符串的好分割数目

给你一个字符串 s ，一个分割被称为「好分割」当它满足：将 s 分割成 2 个字符串 p 和 q ，它们连接起来等于 s 且 p 和 q 中不同字符的数目相同。请你返回 s 中好分割的数目。示例 1：输入： s = "aacaba" 输出： 2 解释：总共有 5 种分割字符串 "aaca…

哈希表字符串动态规划位运算

题目描述

给你一个字符串 s ，一个分割被称为「好分割」当它满足：将 s 分割成 2 个字符串 p 和 q ，它们连接起来等于 s 且 p 和 q 中不同字符的数目相同。

请你返回 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") 。

示例 3：

输入：s = "aaaaa"
输出：4
解释：所有分割都是好分割。

示例 4：

输入：s = "acbadbaada"
输出：2

提示：

s 只包含小写英文字母。
1 <= s.length <= 10^5

lightbulb

解题思路

方法一：哈希表

我们维护两个哈希表，分别记录左侧出现的字符、右侧的字符以及出现的次数。初始时，左侧的哈希表为空，右侧的哈希表为字符串 $s$ 中所有字符出现的次数。

接下来，我们从左到右遍历字符串 $s$ ，对于遍历到的字符 $c$ ，我们将其加入左侧的哈希表，同时将其在右侧的哈希表中的出现次数减一。如果减一后，右侧哈希表中的出现次数为 0，则将其从右侧哈希表中移除。然后，我们判断左侧哈希表中的键值对数量是否与右侧哈希表中的键值对数量相等，如果相等，则将答案加一。

最终，我们返回答案即可。

时间复杂度为 $O(n)$ ，空间复杂度为 $O(n)$ 。其中 $n$ 为字符串 $s$ 的长度。

1

2

3

4

5

6

7

8

9

10

11

12

13

class Solution:
    def numSplits(self, s: str) -> int:
        cnt = Counter(s)
        vis = set()
        ans = 0
        for c in s:
            vis.add(c)
            cnt[c] -= 1
            if cnt[c] == 0:
                cnt.pop(c)
            ans += len(vis) == len(cnt)
        return ans

speed

复杂度分析

指标	值
时间	complexity is O(n) because each character is moved once between leftCount and rightCount. Space complexity is O(1) in practice, as there are at most 26 lowercase letters stored in the hash maps.
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Checking if the candidate updates counts efficiently rather than recomputing distinct letters from scratch.
question_mark
Observing whether the candidate recognizes the problem as a state transition DP pattern with hash maps.
question_mark
Looking for handling of edge cases where strings are too short for any valid split.

warning

常见陷阱

外企场景

error
Recomputing distinct characters for every split, causing O(n^2) time and timeout on large inputs.
error
Forgetting to remove letters from rightCount when their count reaches zero, which inflates the distinct count incorrectly.
error
Ignoring edge cases with minimal string length or repeated characters leading to wrong good split count.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Count good splits when ignoring case sensitivity for letters.
arrow_right_alt
Return all the indices where good splits occur instead of just the count.
arrow_right_alt
Allow Unicode characters, requiring more generic hash maps for character tracking.

help

常见问题

外企场景

继续练习

#691 贴纸拼词 #1371 每个元音包含偶数次的最长子字符串 #1684 统计一致字符串的数目