Pythonでk個の異なる文字を含む最長の部分文字列の長さを見つけるプログラム

数値kと別の文字列sがあるとすると、最大でk個の異なる文字を含む最長の部分文字列のサイズを見つける必要があります。

したがって、入力がk =3 s ="kolkata"の場合、出力は4になります。これは、長さが4の"kolk"と"kata"の3つの異なる文字を持つ2つの最長のサブストリングがあるためです。

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

• ans：=0、左：=0

• テーブル：=新しいマップ

• 右の場合は0からs− 1のサイズの範囲であり、do

  • table [s [right]]：=1 +（存在する場合はs [right]、それ以外の場合は0）

  • テーブルのサイズが<=kの場合、

    • ans：=ansの最大値と（右-左+ 1）

  • それ以外の場合

    • テーブルのサイズが>kの場合、実行

      • left_char：=s [left]

      • table [left_char]が1と同じ場合、

        • テーブルからleft_char番目の要素を削除します

      • それ以外の場合

        • table [left_char]：=table [left_char] − 1

      • 左：=左+ 1

• ansを返す

理解を深めるために、次の実装を見てみましょう-

例

class Solution:
   def solve(self, k, s):
      ans = 0
      left = 0
      table = {}
      for right in range(0, len(s)):
         table[s[right]] = table.get(s[right], 0) + 1
         if len(table) <= k:
            ans = max(ans, right − left + 1)
         else:
            while len(table) > k:
               left_char = s[left]
               if table[left_char] == 1:
                  table.pop(left_char)
               else:
                  table[left_char] −= 1
               left += 1
      return ans
ob = Solution()
k = 3
s = "kolkata"
print(ob.solve(k, s))

入力

"anewcoffeepot"

出力

4