数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
时尚研究
法律研究Python程序：查找最大数量的无重叠子串
假设我们有一个仅包含小写字母的字符串 s，我们需要找到 s 的最大数量的非空子串，这些子串满足以下规则：
子串不重叠。
包含特定字符 ch 的子串必须包含 ch 的所有出现。
我们需要找到满足这两个条件的最大子串数量。如果有多个子串数量相同的解，则返回总长度最小的解。
例如，如果输入为 s = "pqstpqqprrr"，则输出为 ["s","t","rrr"]，因为满足条件的所有可能的子串为 ["pqstpqqprrr", "pqstpqqp", "st", "s", "t", "rrr"]
为了解决这个问题，我们将遵循以下步骤：
right := 对 s 中所有单个字符 ch 的索引位置从右向左排序。
left := 对所有 i ∈ right 的字符 s[i] 的索引列表。
has := 空列表，gen := 空列表。
对于 i 从 0 到 right 的大小 - 1：
将来自 s[right[i]] 的新字符集插入 gen 的末尾。
将来自 s[从索引 (left[i] + 1 到 right[i]-1) - gen 的最后一项] 的子串的新字符集插入 has 的末尾。
对于 j 从 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
对于 ind 从 0 到 has 的大小 - 1：
l := 如果 s[i] 出现在 gen[ind] 中，则所有 i ∈ left 的元素 i 的最小值。
r := 如果 s[i] 出现在 gen[ind] 中，则所有 i ∈ right 的元素 i 的最大值。
如果 p_right < l，则：
将 s[从索引 l 到 r] 的子串插入 res 的末尾。
p_right := r
返回 res
示例
让我们看下面的实现来更好地理解。
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']
562 次浏览
