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

pythonserver side programmingprogramming更新于 2025/9/30 11:24:17

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

因此,如果输入为 s = "ppqprqtqtqt", k = 3,则输出将是 rqtqtqt,因为它的长度为 7。

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

  • N := 26

  • 定义一个函数 is_ok() 。这将需要 count, k

  • val := 0

  • for i in range 0 to N, do

    • if count[i] > 0,则

      • val := val + 1

  • 当 (k >= val) 时返回 true

  • 从主方法中,执行以下操作 −

  • unique := 0,size := s 的大小

  • count := 大小为 N 的数组,用 0 填充

  • 对于从 0 到 size 范围内的 i,执行

    • 如果 s[i] 的计数与 0 相同,则

      • unique := unique + 1

    • 增加计数s[i] 相加 1

  • 如果唯一 < k,则

    • 没有这样的字符并退出

  • start := 0, end := 0

  • window_length := 1, window_start := 0

  • count := 大小为 N 的数组,用 0 填充

  • 将 s[0] 的计数增加 1

  • 对于范围从 1 到 size 的 i,执行

    • 将 s[i] 的计数增加 1

    • end := end + 1

    • 当 is_ok(count, k) 为 false 时,执行

      • 将 s[i] 的数量减少 1

      • start := start + 1

    • 如果 end-start+1 > window_length,则

      • window_length := end-start+1

      • window_start := start

  • 返回 s[从索引 window_start 到 window_start + window_length] 的子字符串

示例

让我们看看下面的实现以便更好地理解 −

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))

输入

"ppqprqtqtqt", 3

输出

rqtqtqt

相关文章


有用资源