在 Python 中查找最大非重叠子串数的程序
假设我们有一个只有小写字母的字符串s，我们必须找到满足以下规则的s的最大非空子串数
子串不重叠
包含特定字符ch的子字符串也必须包含所有出现的ch。
我们必须找到满足这两个条件的最大子串数。如果有多个具有相同子串数量的此类解决方案，则以最小总长度返回该解决方案。
因此，如果输入类似于s="pqstpqqprrr"，那么输出将是["s","t","rrr"]因为所有可能满足条件的子串都是["pqstpqqprrr","pqstpqqp","st","s","t","rrr"]
示例
让我们看下面的实现来更好地理解
def solve(s):
right = sorted([s.rindex(ch) for ch in set(s)])
left = [s.index(s[i]) for i in right]
has, gen = [], []
for i in range(len(right)):
gen.append(set(s[right[i]]))
has.append(set(s[left[i] + 1:right[i]]) - gen[-1])
for j in range(len(has) - 2, -1, -1):
if (has[-1] & gen[j]) and (has[j] & gen[-1]):
gen[-1] = gen[-1] | gen[j]
has[-1] = (has[-1] | has[j]) - gen[-1]
del has[j], gen[j]
res, p_right = [], -1
for ind in range(len(has)):
l = min([i for i in left if s[i] in gen[ind]])
r = max([i for i in right if s[i] in gen[ind]])
if p_right < l:
res.append(s[l : r + 1])
p_right = r
return res
s = "pqstpqqprrr"
print(solve(s))输入
"pqstpqqprrr"输出结果
['s', 't', 'rrr']
热门推荐
10 结婚祝福语亲姐姐简短
11 酒店客人祝福语简短
12 新娘对伴娘祝福语简短
13 小寒健康祝福语大全简短
14 简短有内涵的祝福语
15 薛之谦祝福语简短
16 最美的留言祝福语简短
17 甄嬛传祝福语简短
18 新年的生日祝福语简短