Pythonで2つの異なる要素を持つ最長の部分文字列の長さを見つけるプログラム

文字列sがあるとすると、最大2つの異なる文字を含む最長の部分文字列の長さを見つける必要があります。

したがって、入力がs ="xyzzy"のような場合、出力は4になります。これは、 "yzzy"が、最大2文字の一意の文字を含む最長のサブストリングであるためです。

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

• start：=0

• c：=地図

• ans：=0

• 0からsのサイズまでの範囲で終了する場合は、実行してください

  • c [s [end]]：=c [s [end]] + 1

  • サイズがc>2の場合、実行

    • c [s [start]]：=c [s [start]]-1

      
      

    • c [s [start]]が0の場合、

      • c [s [start]]

        を削除します

    • start：=start + 1

  • ans：=ansの最大値と（end-start + 1）

• ansを返す

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

例

class Solution:
   def solve(self, s):
      from collections import Counter
      start = 0
      c = Counter()
      ans = 0
      for end in range(len(s)):
         c[s[end]] += 1
         while len(c) > 2:
            c[s[start]] -= 1
            if not c[s[start]]:
               del c[s[start]]
            start += 1
         ans = max(ans, end - start + 1)
      return ans
ob = Solution()
s = "xyzzy"
print(ob.solve(s))

入力

s = "xyzzy"

出力

4