Pythonで指定された部分文字列を含む最小文字列サイズを見つけるプログラム

2つの文字列sとtがあるとすると、tのすべての文字を含むsの最小部分文字列のサイズを見つける必要があります。そのような部分文字列が存在しない場合は、-1を返します。

したがって、入力がs ="thegrumpywizardmakes" t ="wake"の場合、 "wake"を含む最短のサブストリングは"wizardmake"（長さ10）であるため、出力は10になります。

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

• カウンター：=bの各文字の頻度

• start：=0

• min_subs：=inf

• rem：=b内の個別の文字の数

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

  • 現在：=a [end]

  • 電流がカウンターにある場合、

    • counter [current]：=counter [current]-1

    • counter [current]が0と同じ場合、

      • rem：=rem-1

  • remは0と同じですが、実行してください

    • prev_char：=a [start]

    • prev_charがカウンターにある場合、

      • counter [prev_char]：=counter [prev_char] + 1

      • counter [prev_char]> 0の場合、

        • rem：=rem + 1

    • min_subs：=最小のmin_subsおよび（end-start + 1）

    • start：=start + 1

• min_subsがinfでない場合は、min_subsを返します。それ以外の場合は-1

例（Python）

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

class Solution:
   def solve(self, a, b):
      counter = {}
      for char in b:
         counter[char] = counter.get(char, 0) + 1
      start = 0
      min_subs = float("inf")
      rem = len(counter)
      for end in range(len(a)):
         current = a[end]
         if current in counter:
            counter[current] -= 1
            if counter[current] == 0:
               rem -= 1
         while rem == 0:
            prev_char = a[start]
            if prev_char in counter:
               counter[prev_char] += 1
               if counter[prev_char] > 0:
                  rem += 1
               min_subs = min(min_subs, end - start + 1)
               start += 1
      return min_subs if min_subs != float("inf") else -1
ob = Solution()
s = "thegrumpywizardmakes"
t = "wake"
print(ob.solve(s, t))

入力

"thegrumpywizardmakes", "wake"

出力

2