파이썬으로 다른 문자열의 모든 문자를 포함하는 최소 크기 부분 문자열 찾기

문제 개요

두 개의 문자열 s1과 s2가 주어졌을 때, s2의 모든 문자를 포함하는 s1 내부의 가장 작은 부분 문자열(윈도우)을 찾아야 합니다.

예를 들어 입력이 s1 = "I am a student", s2 = "mdn"이라면 출력은 "m a studen"이 됩니다. 이 부분 문자열은 'm', 'd', 'n' 세 문자를 모두 포함하면서 길이가 가장 짧기 때문입니다.

해결 접근 방식: 슬라이딩 윈도우 + 해시 카운팅

이 문제는 슬라이딩 윈도우(Sliding Window) 기법과 문자 빈도수 카운팅을 조합하면 효율적으로 해결할 수 있습니다. 핵심 아이디어는 다음과 같습니다.

패턴 문자열(s2)의 각 문자별 필요 개수를 해시 배열에 저장합니다.
왼쪽 포인터(start)와 오른쪽 포인터(j)로 메인 문자열을 순회하며 윈도우를 확장합니다.
필요한 모든 문자가 윈도우에 포함되면(count == patt_len), 왼쪽에서 불필요한 문자를 제거하며 윈도우를 축소합니다.
매 순간의 윈도우 길이를 비교하여 최솟값과 시작 인덱스를 갱신합니다.

알고리즘 단계

N := 256 (ASCII 문자 전체 범위)
str_len := main_str의 길이, patt_len := pattern의 길이
만약 str_len < patt_len이면 None을 반환합니다.
hash_pat과 hash_str 배열을 크기 N으로 생성하고 0으로 채웁니다.
pattern의 각 문자에 대해 hash_pat[ord(pattern[i])] 값을 1씩 증가시킵니다.
start := 0, start_index := -1, min_len := 무한대로 초기화하고, count := 0으로 설정합니다.
j를 0부터 str_len까지 순회하며 다음을 반복합니다.
- hash_str[ord(main_str[j])] 값을 1 증가시킵니다.
- 해당 문자가 패턴에 존재하고(hash_pat 값이 0이 아님), 아직 필요 개수를 초과하지 않았다면(hash_str ≤ hash_pat) count를 1 증가시킵니다.
- count == patt_len이면 모든 문자가 포함된 상태이므로, 왼쪽 끝(start)의 문자가 불필요한 동안(빈도 초과 또는 패턴에 없는 문자) start를 이동시키며 윈도우를 축소합니다.
- 현재 윈도우 길이(len_window = j - start + 1)가 min_len보다 작으면 min_len과 start_index를 갱신합니다.
순회 종료 후 start_index가 여전히 -1이면 조건을 만족하는 부분 문자열이 없으므로 None을 반환합니다.
그렇지 않으면 main_str[start_index : start_index + min_len]을 반환합니다.

구현 예제

다음 파이썬 코드로 위 알고리즘을 구현할 수 있습니다.

N = 256

def get_pattern(main_str, pattern):
    str_len = len(main_str)
    patt_len = len(pattern)

    if str_len < patt_len:
        return None

    hash_pat = [0] * N
    hash_str = [0] * N

    for i in range(patt_len):
        hash_pat[ord(pattern[i])] += 1

    start, start_index, min_len = 0, -1, float('inf')
    count = 0

    for j in range(str_len):
        hash_str[ord(main_str[j])] += 1

        if (hash_pat[ord(main_str[j])] != 0 and
                hash_str[ord(main_str[j])] <= hash_pat[ord(main_str[j])]):
            count += 1

        if count == patt_len:
            while (hash_str[ord(main_str[start])] > hash_pat[ord(main_str[start])]
                   or hash_pat[ord(main_str[start])] == 0):
                if hash_str[ord(main_str[start])] > hash_pat[ord(main_str[start])]:
                    hash_str[ord(main_str[start])] -= 1
                start += 1

            len_window = j - start + 1
            if min_len > len_window:
                min_len = len_window
                start_index = start

    if start_index == -1:
        return None

    return main_str[start_index : start_index + min_len]


main_str = "I am a student"
pattern = "mdn"
print(get_pattern(main_str, pattern))

입력

"I am a student", "mdn"

출력

m a studen

복잡도 분석

시간 복잡도: O(n) — 오른쪽 포인터 j와 왼쪽 포인터 start가 각각 문자열을 한 번씩만 순회하므로 선형 시간에 처리됩니다.
공간 복잡도: O(1) — 고정 크기(256)의 해시 배열 두 개만 사용하므로 상수 공간입니다.