Computer >> 컴퓨터 >  >> 프로그래밍 >> Python

Python으로 문자열에서 서로 다른 문자를 정확히 k개 포함하는 가장 긴 부분 문자열 찾기

문제 개요

하나의 문자열이 주어졌을 때, 서로 다른 문자를 정확히 k개만 포함하는 가장 긴 부분 문자열(substring)을 구하는 문제입니다. 만약 최대 길이를 가지는 부분 문자열이 여러 개 존재한다면, 그중 아무거나 하나를 반환하면 됩니다.

예를 들어 입력이 다음과 같다고 가정해 보겠습니다.

  • s = "ppqprqtqtqt", k = 3

이 경우 출력은 rqtqtqt가 됩니다. 이 부분 문자열의 길이는 7이며, r, q, t라는 세 종류의 고유한 문자를 정확히 포함하기 때문입니다.

접근 방법: 슬라이딩 윈도우(Sliding Window)

이 문제는 투 포인터 기법 중 하나인 슬라이딩 윈도우 방식으로 효율적으로 해결할 수 있습니다. 알고리즘의 전체 흐름은 다음과 같습니다.

  1. N = 26으로 설정합니다(소문자 알파벳 기준).

  2. is_ok(count, k) 함수를 정의합니다. 현재 윈도우 내 고유 문자 수가 k개 이하인지 확인하는 역할을 합니다.

    • val := 0으로 초기화한 뒤, count 배열에서 0보다 큰 값의 개수를 셉니다.
    • k >= val이면 True를 반환합니다.

  3. 메인 로직에서 다음 단계를 수행합니다.

    • unique := 0으로 초기화하고, size는 문자열 s의 길이로 설정합니다.
    • 크기 N의 count 배열을 0으로 초기화합니다.
    • 전체 문자열을 순회하며 각 문자의 등장 횟수를 세고, 처음 등장한 문자라면 unique 값을 1 증가시킵니다.
    • 만약 unique < k라면, 문자열에 서로 다른 문자가 k개 미만이라는 의미이므로 조건을 만족하는 부분 문자열이 존재하지 않습니다. 이 경우 적절한 메시지를 반환하고 종료합니다.

  4. start와 end 포인터를 0으로 초기화하고, window_length := 1, window_start := 0으로 설정합니다.

  5. count 배열을 다시 초기화하고 첫 번째 문자의 개수를 1로 만듭니다.

  6. 두 번째 문자부터 끝까지 순회하면서 다음을 반복합니다.

    • 현재 문자의 count를 1 증가시키고 end를 1 증가시킵니다.
    • is_ok(count, k)가 False인 동안(start 지점의 문자를 제거해도 되는 동안) start 위치의 문자 count를 감소시키고 start를 앞으로 이동시킵니다.
    • 현재 윈도우 길이(end - start + 1)가 window_length보다 크다면, window_length와 window_start를 갱신합니다.

  7. 최종적으로 window_start 위치에서 window_length 길이만큼의 부분 문자열을 반환합니다.

구현 예제

아래는 위 알고리즘을 Python으로 구현한 코드입니다.

N = 26

def is_ok(count, k):
    val = 0
    for i in range(N):
        if count[i] > 0:
            val += 1
    return (k >= val)

def k_unique_chars(s, k):
    unique = 0
    size = len(s)
    count = [0] * N
    for i in range(size):
        if count[ord(s[i]) - ord('a')] == 0:
            unique += 1
        count[ord(s[i]) - ord('a')] += 1
    if unique < k:
        return "Not sufficient characters"

    start = 0
    end = 0
    window_length = 1
    window_start = 0
    count = [0] * len(count)
    count[ord(s[0]) - ord('a')] += 1

    for i in range(1, size):
        count[ord(s[i]) - ord('a')] += 1
        end += 1
        while not is_ok(count, k):
            count[ord(s[start]) - ord('a')] -= 1
            start += 1
        if end - start + 1 > window_length:
            window_length = end - start + 1
            window_start = start

    return s[window_start:window_start + window_length]

s = "ppqprqtqtqt"
k = 3
print(k_unique_chars(s, k))

입력

"ppqprqtqtqt", 3

출력

rqtqtqt

복잡도 분석

  • 시간 복잡도: O(n). 각 문자는 start와 end 포인터에 의해 최대 두 번씩 처리되므로 선형 시간에 동작합니다.
  • 공간 복잡도: O(N), 즉 알파벳 개수(26)에 해당하는 고정 크기의 배열만 사용하므로 사실상 O(1)입니다.

마무리

슬라이딩 윈도우 기법은 문자열에서 조건을 만족하는 연속 구간을 찾는 문제에 매우 유용합니다. 이번 문제처럼 "고유 문자의 개수 제한"과 같은 조건이 있을 때, 두 개의 포인터를 활용해 윈도우를 확장하고 축소하는 방식을 익혀두면 다양한 변형 문제에도 쉽게 대응할 수 있습니다.