在 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']