拆分字符串使唯一子字符串的数目最大 图解题解

这道题到底在问什么

输入

s = "ababccc"

输出

5 (一种切法 a, b, ab, c, cc)

输入

s = "aba"

输出

2 (一种切法 a, ba)

输入

s = "aa"

输出

1 (切成 a, a 两段会重复, 只能整段)

最优解：一步一步想明白

1. 3记牢这套:每个位置从短到长尝试切段,段重复就跳过、不重复就切下去递归,到末尾用段数更新答案;再用「已切段数加剩余字符数」当上界剪枝。下面每一帧都在套它。
2. 4先看画面怎么摆。最上面这排 a、b、a、b 是原串 "abab" 的四个字符,谁被前面切走的段吃掉了,就变灰。中间「当前路径 path」是已经切下来的各段,它们必须两两不同,所以这一行同时就是我们去重用的集合。右边「已收集的结果 res」只记下能刷新最多段数的完整切法。我们从位置 0 开始尝试各种切法,追不过当前最多段数的分支会被直接剪掉,最后留下段数最多的那条。
3. 5从位置 0 起手,先试最短的一刀,只切一个字符 a。path 现在是空的,a 没出现过,不重复,可以切。
4. 6把 a 收进 path,集合变成只有 a,指针推进到位置 1,字符 a 变灰表示已经被吃掉,接着去切后面的 bab。
5. 7位置 1 还是先试一个字符 b。当前 path 里只有 a,没有 b,不重复,切下来。
6. 8b 收进 path,集合是 a 和 b 两段,指针到位置 2,前两个字符都变灰,只剩 ab 没切。
7. 9位置 2 先试一个字符 a。可是 path 里已经有 a 了,题目要求各段互不相同,这一刀切出来是重复段,作废,给它打个叉跳过。
8. 10那就把这一段往右延一个字符,变成 ab。path 里没有 ab,不重复,这一刀可以切。
9. 11ab 收进 path,指针正好走到字符串末尾,四个字符全变灰,一种完整切法成型:a 加 b 加 ab,三段全不一样,记进结果区。当前最优答案从 0 抬到 3。
10. 12这条分支到底了,往回退。先撤掉 ab、再撤掉 b,集合退回只剩 a,指针回到位置 1。刚才在这里只试过「切一个字符 b」,现在换更长的切法接着试。
11. 13在位置 1 改切两个字符 ba。path 里只有 a,没有 ba,不重复,切下来。
12. 14ba 收进 path,集合是 a 和 ba 两段,指针到位置 3,只剩最后一个字符 b 没切。
13. 15进下一层前先估个上界。已经切了 2 段,后面就剩 1 个字符,哪怕它单独成段,这条路最多也就 3 段。3 段追不过当前最优的 3 段,再往下也不可能更好,直接剪掉这条路。
14. 16撤掉 ba,回到位置 1,试最长的一刀 bab,一口气切到末尾。path 里没有 bab,不重复,可以切。
15. 17bab 切下去,指针到了末尾,这条路是 a 加 bab 两段。进这一层前先估上界:已切 2 段加剩 0 个字符等于 2,不超过当前最优的 3 段,直接剪掉,不记进结果区。
16. 18以 a 打头的分支都处理完了,能更优的留下、追不过 3 段的都剪掉,把 path 一路退到空,指针回到最开头。第一刀只试过「切一个字符 a」,现在换更长的第一刀接着试。
17. 19第一刀这次切两个字符 ab。path 是空的,当然不重复,切下来,指针推进到位置 2。
18. 20又到估上界的时候。已经切了 1 段,后面还剩 2 个字符,最多再添 2 段,合起来顶多 3 段。还是追不过当前最优的 3,剪掉。
19. 21撤掉 ab,第一刀再加长成 aba。path 空着,不重复,切下来,指针到位置 3。
20. 22继续估上界。已切 1 段,后面只剩 1 个字符,最多再添 1 段,顶多 2 段,更追不过 3 了,剪掉。
21. 23撤掉 aba,第一刀直接把整串 abab 当成一段切到底,path 空着不重复,切下来,指针到末尾。
22. 24整串当成一段,指针到了末尾,这条路只有 1 段。估上界:已切 1 段加剩 0 个字符等于 1,追不过当前最优的 3 段,剪掉,不记进结果区。
23. 25搜索到此结束。结果区里稳稳留下的只有 a、b、ab 这一条 3 段切法;其余每条路要么撞上重复段、要么估上界追不过 3 段被剪掉。这就证明了再也切不出超过 3 段的方案,所以答案就是 3。把 "abab" 切成 a、b、ab 三段,正是唯一子串数目最多的方案,跟开头说的对上了。

⚠️ 容易写错的地方

完整代码（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 TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next
class Solution:
    def maxUniqueSplit(self, s: str) -> int:
        def dfs(i: int):
            nonlocal ans
            if len(st) + len(s) - i <= ans:
                return
            if i >= len(s):
                ans = max(ans, len(st))
                return
            for j in range(i + 1, len(s) + 1):
                if s[i:j] not in st:
                    st.add(s[i:j])
                    dfs(j)
                    st.remove(s[i:j])

        ans = 0
        st = set()
        dfs(0)
        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 <optional>
#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;
struct TreeNode {
  int val;
  TreeNode *left;
  TreeNode *right;
  TreeNode() : val(0), left(nullptr), right(nullptr) {}
  TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
  TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};
struct ListNode {
  int val;
  ListNode *next;
  ListNode() : val(0), next(nullptr) {}
  ListNode(int x) : val(x), next(nullptr) {}
  ListNode(int x, ListNode *next) : val(x), next(next) {}
};
class Solution {
public:
    int maxUniqueSplit(string s) {
        unordered_set<string> st;
        int n = s.size();
        int ans = 0;
        function<void(int)> dfs = [&]( int i ) -> void {
            if (st.size() + n - i <= ans) {
                return;
            }
            if (i >= n) {
                ans = max(ans, (int) st.size());
                return;
            }
            for (int j = i + 1; j <= n; ++j) {
                string t = s.substr(i, j - i);
                if (st.find(t) == st.end()) {
                    st.insert(t);
                    dfs(j);
                    st.erase(t);
                }
            }
        };
        dfs(0);
        return ans;
    }
};

import java.util.*;
class TreeNode { int val; TreeNode left; TreeNode right; TreeNode(){} TreeNode(int val){this.val=val;} TreeNode(int val, TreeNode left, TreeNode right){this.val=val;this.left=left;this.right=right;} }
class ListNode { int val; ListNode next; ListNode(){} ListNode(int val){this.val=val;} ListNode(int val, ListNode next){this.val=val;this.next=next;} }
class Solution {
    private Set<String> st = new HashSet<>();
    private int ans;
    private String s;

    public int maxUniqueSplit(String s) {
        this.s = s;
        dfs(0);
        return ans;
    }

    private void dfs(int i) {
        if (st.size() + s.length() - i <= ans) {
            return;
        }
        if (i >= s.length()) {
            ans = Math.max(ans, st.size());
            return;
        }
        for (int j = i + 1; j <= s.length(); ++j) {
            String t = s.substring(i, j);
            if (st.add(t)) {
                dfs(j);
                st.remove(t);
            }
        }
    }
}

复杂度

面试官可能追问