查找具有k个唯一字母的最大可能子字符串(递归的）

Question

我试图找到最大的子串可能与k唯一的字母。有没有一种方法可以通过字符串分区递归完成？ 我的想法是通过剪切最后一个字符来划分字符串，如果我找到第一个子字符串包含k个唯一字母，我将返回它

For example k = 2, string = "abccd"
abccd ->
abcc, bccd ->
abc,bcc,bcc,ccd -> return bcc

def unique_l(sub, k):
    u=0
    visited = set()
    for ch in sub:
        if ch not in visited:
            visited.add(ch)
            u += 1

    if u < k:
        return -1
    elif u == k:
        return 1
    else:
        return 0


def find_sub(string,k):

    if unique_l(string,k) == 1:
        return string
    if unique_l(string,k) == -1:
        return "Not Found"

    find_sub(string[0:len(string)-1],k) # Left
    find_sub(string[1:len(string)],k) # Right

我知道我可以使用迭代在O（n）时间内完成，但是有没有一种方法可以递归完成呢

Answer 1

可以对生成器使用递归：

from collections import Counter
def group(d, k):
  for i in range(len(d)):
    for b in range(i, len(d)):
       if len(set((_r:=d[i:b]))) == k:
          yield _r
       yield from group(_r, k)


r = max(group("abccd", 2), key=len)

输出：

'bcc'