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