跳至主要內容

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

ITCharge大约 2 分钟

1593. 拆分字符串使唯一子字符串的数目最大open in new window

  • 标签:哈希表、字符串、回溯
  • 难度:中等

题目大意

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

要求:拆分该字符串,并返回拆分后唯一子字符串的最大数目。

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

解题思路

维护一个全局变量 ans 用于记录拆分后唯一子字符串的最大数目。并使用集合 s_set 记录不重复的子串。

  • 从下标为 0 开头的子串回溯。

  • 对于下标为 index 开头的子串,我们可以在 index + 1 开始到 len(s) - 1 的位置上,分别进行子串拆分,将子串拆分为 s[index: i + 1]

  • 如果当前子串不在 s_set 中,则将其存入 s_set 中,然后记录当前拆分子串个数,并从 i + 1 的位置进行下一层递归拆分。然后在拆分完,对子串进行回退操作。

  • 如果拆到字符串 s 的末尾,则记录并更新 ans

  • 在开始位置还可以进行以下剪枝:如果剩余字符个数 + 当前子串个数 <= 当前拆分后子字符串的最大数目,则直接返回。

最后输出 ans

代码

class Solution:
    ans = 0
    def backtrack(self, s, index, count, s_set):
        if len(s) - index + count <= self.ans:
            return 
        if index >= len(s):
            self.ans = max(self.ans, count)
            return

        for i in range(index, len(s)):
            sub_s = s[index: i + 1]
            if sub_s not in s_set:
                s_set.add(sub_s)
                self.backtrack(s, i + 1, count + 1, s_set)
                s_set.remove(sub_s)


    def maxUniqueSplit(self, s: str) -> int:
        s_set = set()
        self.ans = 0
        self.backtrack(s, 0, 0, s_set)
        return self.ans