Pythonで特定の文字列に含まれるk個の一意の文字を含む最長の部分文字列を検索します

文字列があるとすると、正確にk個の一意の文字を持つ可能な限り長い部分文字列を返す必要があります。可能な限り長い長さの部分文字列が複数ある場合は、それらのいずれかを返します。

したがって、入力がs ="ppqprqtqtqt"、k =3の場合、長さ7であるため、出力はrqtqtqtになります。

これを解決するには、次の手順に従います-

• N：=26

• 関数is_ok（）を定義します。これには数えられます、k

• val：=0

• 0からNの範囲のiの場合、実行

  • count [i]> 0の場合、

    • val：=val + 1

• （k> =val）

  の場合にtrueを返します

• メインの方法から、次のようにします-

• 一意：=0、サイズ：=sのサイズ

• count：=サイズNの配列、0で埋める

• 0からサイズの範囲のiの場合、実行

  • s [i]の数が0と同じ場合、

    • ユニーク：=ユニーク+1

  • s[i]の数を1つ増やします

• 一意の場合

  • そのようなキャラクターはなく、終了します

• 開始：=0、終了：=0

• window_length：=1、window_start：=0

• count：=サイズNの配列、0で埋める

• s[0]の数を1増やします

• 1からサイズの範囲の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