在Python中查找非重叠子串的最大数量的程序

假设我们有一个仅包含小写字母的字符串s，我们必须找到满足以下规则的s的非空子串的最大数量

子串是不重叠的
包含特定字符ch的子串必须包含ch的所有出现。

我们必须找到符合这两个条件的最大数量的子串。如果有多个具有相同子串数量的解决方案，则返回具有最小总长度的解决方案。

因此，如果输入是s =“pqstpqqprrr”，则输出将是[“s”，”t”，”rrr”]，因为符合条件的所有可能子串为[“pqstpqqprrr”，“pqstpqqp”，“st”，“s”，“t”，“rrr”]

为了解决这个问题，我们将遵循以下步骤：

right := 排序s右侧所有单个字符ch的索引位置列表
left := 包含所有在right内的s [i]的索引的列表
has := 空列表，gen := 空列表
对于范围0到右侧大小-1中的i，做以下操作
- 在gen的末尾插入来自s [right [i]]的一组新字符
- 在has的末尾插入s [from index（left [i] +1到right [i] -1]子串的一组新字符- gen的最后一项)
- 对于从has的大小- 2到0的范围，按递减顺序执行以下操作
  - 如果（has的最后一项AND gen [j]）和（has [j] AND gen的最后一项）为非零，则
  - gen的最后一项:= gen的最后一项OR gen [j]
  - has的最后一项:=（has的最后一项OR has [j]）- gen的最后一项
  - 删除has [j]，gen [j]
res := 新列表，p_right := -1
对于范围0到has大小的ind-1，执行以下操作
- 如果gen [ind]中存在s [i]，则s的元素i列表中的i的最小值为l
- 如果s [i]位于gen [ind]]中，则i的元素列表i的最大值为r
- 如果p_right
  - 在res的末尾插入s [从索引l到r的子字符串]
  - p_right := r
返回res

例子

让我们看看以下实现，以更好地理解

def solve(s):
    right = sorted([s.rindex(ch) for chin 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))