用 Python 编写程序来查找不重叠子字符串的最大数量

pythonserver side programmingprogramming更新于 2025/12/1 2:20:17

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

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

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

因此，如果输入为 s = "pqstpqqprrr"，则输出将为 ["s","t","rrr"]，因为所有满足条件的可能子字符串都是 ["pqstpqqprrr", "pqstpqqp", "st", "s", "t", "rrr"]

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

right := 从 s 的右侧对所有单个字符 ch 的索引位置列表进行排序
left := 字符索引列表s[i] 对所有在 right 中的 i
has := 一个空列表，gen := 一个空列表
对于范围在 0 到 right 的大小 - 1 内的 i，执行
- 在 gen 的末尾插入一组来自 s[right[i]] 的新字符
- 在 has 的末尾插入一组来自 s[从索引 (left[i] + 1 到 right[i]-1] - gen 的最后一项) 的子字符串的新字符
- 对于范围在 has 的大小 - 2 到 0 内的 j，减少 1，执行
  - 如果 (has 的最后一项 AND gen[j]) 和 (has[j] AND gen 的最后一项) 非零，则
    - gen 的最后一项 := gen 的最后一项或 gen[j]
    - has 的最后一项 :=(has 的最后一项或 has[j]) - gen 的最后一项
    - 删除 has[j]、gen[j]
res := 一个新的列表，p_right := -1
对于 ind，范围从 0 到 has 的大小 - 1，执行
- 如果 s[i] 存在于 gen[ind] 中，则 l := 元素 i 列表中所有左侧 i 的最小值
- 如果 s[i] 存在，则 r := 元素 i 列表中所有右侧 i 的最大值in gen[ind]]
- 如果 p_right < l，则
  - 在 res 末尾插入 s[从索引 l 到 r] 的子字符串
  - 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))