5520. 拆分字符串使唯一子字符串的数目最大 [medium]
5520. 拆分字符串使唯一子字符串的数目最大 [medium]
给你一个字符串 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 仅包含小写英文字母
First Try
2020-09-20
用贪心算法的错误摸索见Failed Try中的描述，后来用暴力法直接搞定。
给予字符串长度只有16，用暴力法显然没有什么问题。因为每个拆分的单词按start_index和end_index来标记的话，最多也只有一个n * n矩阵的可能性, 因此复杂度不会超过O(n^2)。
暴力破解法就是backtrack遍历，只统计到最后子字符串为空的情况，若最后子字符串无法再被拆分本身也无效，则不会进行统计。
字符串的各种题目真是有点心结了，淡定淡定。
class Solution:
def maxUniqueSplit(self, s: str) -> int:
# 暴力法？
splitted = set()
rv = dict(maxv = 0)
def backtrack(parts, splitted, rv):
if len(parts) == 0:
rv["maxv"] = max(rv["maxv"], len(splitted))
for i in range(1, len(parts) + 1):
if parts[:i] not in splitted:
splitted.add(parts[:i])
backtrack(parts[i:], splitted, rv)
splitted.remove(parts[:i])
backtrack(s, splitted, rv)
return rv["maxv"]
Failed Try
2020-09-20
一开始以为可以用贪心算法来做，先找到的最短的不存在的单词就填写进去，如果最后凑不齐再往回找补。几个测试案例都通过了，但总觉得理论上不够严谨，不知道是否有例外情况。提交上去，发现真的错误了，没法用贪心算法来做。
比如对于测试案例"addbsd"，按照贪心算法的结果是"a, d,db, sd",答案为4；但准确拆分结果应该是"a, dd, b, s, d"，答案为5。可以看出最开始的最优，并不是全局的最优。
对于这种字母串题目和贪心算法，总是担心有情况没考虑到，尤其是当自己觉得不应该是贪心算法，而最后被证明应该是贪心算法。
还好这道题并不是，于是可以考虑用其他方法来求解了，比如暴力法，毕竟字符串总长度才16。
class Solution:
def maxUniqueSplit(self, s: str) -> int:
sidx, eidx = 0, 1
splitted = []
while eidx <= len(s):
if s[sidx: eidx] not in splitted:
splitted.append(s[sidx: eidx])
sidx = eidx
eidx += 1
else:
eidx += 1
if sidx != len(s):
reserve = s[sidx: eidx]
while reserve in splitted:
reserve = splitted.pop() + reserve
splitted.append(reserve)
print(splitted)
return len(splitted)