字符串的好分割数目 图解题解

这道题到底在问什么

输入

s = "aacaba"

输出

2(切点 "aac|aba":左右都 2 种字符;切点 "aaca|ba":左右都 2 种字符)

输入

s = "abcd"

输出

1(只有 "ab|cd" 左右各 2 种)

最优解：一步一步想明白

1. 3记牢一句话:左段的集合往大长,右段的计数往小缩,两边不同数一相等就是一个好分割。下面每一帧都在套这个思路。
2. 4开滑之前先看舞台。上面这排是字符串 "aacaba" 的每个字符。右边面板是右段计数 cnt,现在分界线还在最左边,左段是空的、右段就是整串,所以 cnt 里记着整串的字符:a 有 4 个、c 有 1 个、b 有 1 个,一共 3 种不同字符,这就是右段当前的不同数。左段集合 vis 现在空空如也,不同数是 0。
3. 5说清楚滑动规则。分界线会从最左边一格一格往右挪。每当它滑过一个字符,这个字符就从右段交接到左段:一方面把它加进左段集合 vis,另一方面把右段计数 cnt 里对应的那一格减一。减到 0 就代表这个字符在右段彻底没了,要把那一行删掉。挪一步、比一次两边的不同数,相等就攒一个好分割。下面正式开滑。
4. 6分界线滑到下标 0,把字符 "a" 交接给左段。左段集合 vis 之前没有 "a",这一加就多了一种字符,左段不同数变成 1,现在左段是 {a}。
5. 7同一个字符 "a" 从右段走掉了一个,所以把右段计数里它那一格减一,从 4 变成 3。还没减到 0,"a" 在右段后面还会出现,所以这一行保留,右段不同数仍是 3。右段不同数只在某字符彻底清零时才会降。
6. 8左段是 "a",右段是 "acaba"。左段不同数 1,右段不同数 3。两边不相等,这个切点不算好分割,ans 保持 0,继续往右滑。
7. 9分界线滑到下标 1,把字符 "a" 交接给左段。左段集合 vis 早就有 "a" 了,再加也是同一个,所以集合不变,左段不同数还是 1,仍是 {a}。这一步告诉你,左段不同数只在遇到全新字符时才会涨。
8. 10同一个字符 "a" 从右段走掉了一个,所以把右段计数里它那一格减一,从 3 变成 2。还没减到 0,"a" 在右段后面还会出现,所以这一行保留,右段不同数仍是 3。右段不同数只在某字符彻底清零时才会降。
9. 11左段是 "aa",右段是 "caba"。左段不同数 1,右段不同数 3。两边不相等,这个切点不算好分割,ans 保持 0,继续往右滑。
10. 12分界线滑到下标 2,把字符 "c" 交接给左段。左段集合 vis 之前没有 "c",这一加就多了一种字符,左段不同数变成 2,现在左段是 {a, c}。
11. 13同一个字符 "c" 从右段走掉了一个,所以把右段计数里它那一格减一,从 1 变成 0。减到 0 了,说明 "c" 在右段一个都不剩,要把这一行从表里删掉。表里少一行,右段不同数就降到 2。
12. 14左段是 "aac",右段是 "aba"。左段不同数 2,右段不同数 2。两边正好相等,这个切点是好分割,ans 加一变成 1。屏幕上绿色高亮的就是这次切出的左段。
13. 15分界线滑到下标 3,把字符 "a" 交接给左段。左段集合 vis 早就有 "a" 了,再加也是同一个,所以集合不变,左段不同数还是 2,仍是 {a, c}。这一步告诉你,左段不同数只在遇到全新字符时才会涨。
14. 16同一个字符 "a" 从右段走掉了一个,所以把右段计数里它那一格减一,从 2 变成 1。还没减到 0,"a" 在右段后面还会出现,所以这一行保留,右段不同数仍是 2。右段不同数只在某字符彻底清零时才会降。
15. 17左段是 "aaca",右段是 "ba"。左段不同数 2,右段不同数 2。两边正好相等,这个切点是好分割,ans 加一变成 2。屏幕上绿色高亮的就是这次切出的左段。
16. 18分界线滑到下标 4,把字符 "b" 交接给左段。左段集合 vis 之前没有 "b",这一加就多了一种字符,左段不同数变成 3,现在左段是 {a, c, b}。
17. 19同一个字符 "b" 从右段走掉了一个,所以把右段计数里它那一格减一,从 1 变成 0。减到 0 了,说明 "b" 在右段一个都不剩,要把这一行从表里删掉。表里少一行,右段不同数就降到 1。
18. 20左段是 "aacab",右段是 "a"。左段不同数 3,右段不同数 1。两边不相等,这个切点不算好分割,ans 保持 2,继续往右滑。
19. 21分界线滑到下标 5,把字符 "a" 交接给左段。左段集合 vis 早就有 "a" 了,再加也是同一个,所以集合不变,左段不同数还是 3,仍是 {a, c, b}。这一步告诉你,左段不同数只在遇到全新字符时才会涨。
20. 22同一个字符 "a" 从右段走掉了一个,所以把右段计数里它那一格减一,从 1 变成 0。减到 0 了,说明 "a" 在右段一个都不剩,要把这一行从表里删掉。表里少一行,右段不同数就降到 0。
21. 23左段是 "aacaba",右段是 "空"。左段不同数 3,右段不同数 0。分界线已经滑到末尾,右段是空的、不同数 0,这不是一个真正的切点,自然不相等,ans 保持 2。这一帧顺便说明:右段为空时永远配不上非空的左段,所以最后这一格不会误判成好分割。
22. 24分界线滑到了最右边,右段计数全部清空,所有字符都交接给了左段。回放一下:整条路上只有两个切点让左右两段的不同数相等,分别是 "aac | aba" 和 "aaca | ba",这两个切点左右两段都各有 2 种不同字符。所以好分割一共 2 个。全程只把字符串扫了一遍,每一步只做并入、减一、比较三个常数操作。

⚠️ 容易写错的地方

完整代码（Python / C++ / Java）

from __future__ import annotations
from typing import *
from collections import *
from functools import *
from itertools import *
from math import *
from heapq import *
from bisect import *
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

#include <algorithm>
#include <array>
#include <cctype>
#include <climits>
#include <cmath>
#include <deque>
#include <functional>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
using namespace std;
class Solution {
public:
    int numSplits(string s) {
        unordered_map<char, int> cnt;
        for (char& c : s) {
            ++cnt[c];
        }
        unordered_set<char> vis;
        int ans = 0;
        for (char& c : s) {
            vis.insert(c);
            if (--cnt[c] == 0) {
                cnt.erase(c);
            }
            ans += vis.size() == cnt.size();
        }
        return ans;
    }
};

import java.util.*;
class Solution {
    public int numSplits(String s) {
        Map<Character, Integer> cnt = new HashMap<>();
        for (char c : s.toCharArray()) {
            cnt.merge(c, 1, Integer::sum);
        }
        Set<Character> vis = new HashSet<>();
        int ans = 0;
        for (char c : s.toCharArray()) {
            vis.add(c);
            if (cnt.merge(c, -1, Integer::sum) == 0) {
                cnt.remove(c);
            }
            if (vis.size() == cnt.size()) {
                ++ans;
            }
        }
        return ans;
    }
}

复杂度

面试官可能追问