How do I optimize the backtracking search for unique substrings?

You optimize the search by using a hash set to track which substrings have been used, enabling O(1) checks and pruning of duplicate branches during backtracking.

What is the time complexity of this problem?

The time complexity is O(n^2 * 2^n), as we explore all possible substring combinations and check each for uniqueness.

What happens if I don't use pruning during backtracking?

Without pruning, the algorithm would explore duplicate substrings, leading to redundant computations and higher time complexity.

What is the space complexity of this problem?

The space complexity is O(n) due to the hash set storing substrings and the recursion stack during backtracking.

Can I extend this problem to work with non-alphabet characters?

Yes, the problem can be extended to work with strings containing any characters, as long as the backtracking approach and hash set management are adapted to handle them.

#1593

Medium

auto_awesome回溯·pruning

LeetCode 题解工作台

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

给你一个字符串 s ，请你拆分该字符串，并返回拆分后唯一子字符串的最大数目。字符串 s 拆分后可以得到若干非空子字符串，这些子字符串连接后应当能够还原为原字符串。但是拆分出来的每个子字符串都必须是唯一的。注意：子字符串是字符串中的一个连续字符序列。示例 1：输入： s = "ab…

哈希表字符串回溯

题目描述

给你一个字符串 s ，请你拆分该字符串，并返回拆分后唯一子字符串的最大数目。

字符串 s 拆分后可以得到若干 非空子字符串 ，这些子字符串连接后应当能够还原为原字符串。但是拆分出来的每个子字符串都必须是 唯一的 。

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

示例 1：

输入：s = "ababccc"
输出：5
解释：一种最大拆分方法为 ['a', 'b', 'ab', 'c', 'cc'] 。像 ['a', 'b', 'a', 'b', 'c', 'cc'] 这样拆分不满足题目要求，因为其中的 'a' 和 'b' 都出现了不止一次。

示例 2：

输入：s = "aba"
输出：2
解释：一种最大拆分方法为 ['a', 'ba'] 。

示例 3：

输入：s = "aa"
输出：1
解释：无法进一步拆分字符串。

提示：

1 <= s.length <= 16
s 仅包含小写英文字母

lightbulb

解题思路

方法一：回溯 + 剪枝

我们定义一个哈希表 $\textit{st}$ ，用于存储当前已经拆分出的子字符串。然后我们使用深度优先搜索的方式，尝试将字符串 $\textit{s}$ 拆分成若干个唯一的子字符串。

具体地，我们设计一个函数 $\text{dfs}(i)$ ，表示我们正在考虑将 $\textit{s}[i:]$ 进行拆分。

在函数 $\text{dfs}(i)$ 中，我们首先判断如果当前已经拆分出的子字符串的数量加上剩余的字符数小于等于当前的答案，那么我们就没有必要继续拆分，直接返回。如果 $i \geq n$ ，那么说明我们已经完成了对整个字符串的拆分，我们更新答案为当前的子字符串数量和答案的较大值。否则，我们枚举当前子字符串的结束位置 $j$ （不包括 $j$ ），并判断 $\textit{s}[i..j)$ 是否已经被拆分出来。如果没有被拆分出来，我们将其加入到哈希表 $\textit{st}$ 中，并继续递归地考虑拆分剩余的部分。在递归调用结束后，我们需要将 $\textit{s}[i..j)$ 从哈希表 $\textit{st}$ 中移除。

最后，我们返回答案。

时间复杂度 $O(n^2 \times 2^n)$ ，空间复杂度 $O(n)$ 。其中 $n$ 为字符串 $\textit{s}$ 的长度。

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

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

speed

复杂度分析

指标	值
时间	O(n^2 \cdot 2^n)
空间	O(n)

psychology

面试官常问的追问

外企场景

question_mark
Look for understanding of recursive backtracking and pruning techniques.
question_mark
Check the candidate's ability to optimize space and time complexity using a set for uniqueness tracking.
question_mark
Ensure familiarity with managing recursive states and backtracking tree exploration.

warning

常见陷阱

外企场景

error
Forgetting to prune duplicates properly, leading to redundant computations.
error
Not managing the recursion state efficiently, causing unnecessary recomputation of results.
error
Misunderstanding the problem requirements, such as assuming substrings can repeat.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Limit the length of the substrings (e.g., substrings must be at least 2 characters long).
arrow_right_alt
Extend the problem to work with strings containing uppercase letters or non-alphabetical characters.
arrow_right_alt
Change the problem to return the substrings instead of their count, requiring a different approach.

help

常见问题

外企场景

继续练习

#1980 找出不同的二进制字符串 #1079 活字印刷 #691 贴纸拼词