파이썬에서 주어진 부분 문자열을 포함하는 최소 문자열 크기를 찾는 프로그램

<시간/>

두 개의 문자열 s와 t가 있다고 가정하고 t의 모든 문자를 포함하는 s에서 최소 부분 문자열의 크기를 찾아야 합니다. 그러한 하위 문자열이 존재하지 않으면 -1을 반환합니다.

따라서 입력이 s ="thegrumpywizardmakes" t ="wake"와 같으면 "wake"를 포함하는 가장 짧은 부분 문자열이 "wizardmake"(길이 10)이므로 출력은 10이 됩니다.

이 문제를 해결하기 위해 다음 단계를 따릅니다. −

counter :=b의 각 문자의 빈도
시작 :=0
min_subs :=정보
rem :=b의 고유 문자 수
범위 0에서 크기까지의 경우
- 현재 :=a[종료]
- 전류가 카운터에 있으면
  - 카운터[현재] :=카운터[현재] - 1
  - counter[current]가 0과 같으면
    - 렘 :=렘 - 1
- rem이 0인 동안 do
  - prev_char :=a[시작]
  - prev_char가 카운터에 있으면
    - 카운터[이전_문자] :=카운터[이전_문자] + 1
    - counter[prev_char]> 0이면
      - 렘 :=렘 + 1
  - min_subs :=min_subs의 최소값 및 (end - start + 1)
  - 시작 :=시작 + 1
min_subs가 inf가 아니면 min_subs를 반환하고 그렇지 않으면 -1

예제(파이썬)

이해를 돕기 위해 다음 구현을 살펴보겠습니다. −

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"