在Python中的给定字符串中找到具有k个唯一字符的最长子字符串

Z时代
2024-01-10
分类：综合

假设我们有一个字符串，我们必须返回具有恰好 k 个唯一字符的最长可能子字符串，如果有多个最长可能长度的子字符串，则返回其中任何一个。

因此，如果输入类似于 s = "ppqprqtqtqt", k = 3，那么输出将是 rqtqtqt，因为它的长度为 7。

在线示例

让我们看看以下实现以获得更好的理解 -

N = 26
def is_ok(count, k):
   val = 0
   for i in range(N):
      if count[i] > 0:
         val += 1
   return (k >= val)
def k_unique_chars(s, k):
   unique = 0
   size = len(s)
   count = [0] * N
   for i in range(size):
      if count[ord(s[i])-ord('a')] == 0:
         unique += 1
      count[ord(s[i])-ord('a')] += 1
   if unique < k:
      return "Not sufficient characters"
   start = 0
   end = 0
   window_length = 1
   window_start = 0
   count = [0] * len(count)
   count[ord(s[0])-ord('a')] += 1
   for i in range(1,size):
      count[ord(s[i])-ord('a')] += 1
      end+=1
      while not is_ok(count, k):
         count[ord(s[start])-ord('a')] -= 1
         start += 1
      if end-start+1 > window_length:
         window_length = end-start+1
         window_start = start
   return s[window_start:window_start + window_length]
s = "ppqprqtqtqt"
k = 3
print(k_unique_chars(s, k))