Python – K개의 고유한 문자를 가진 길이 N의 부분 문자열 추출하기

파이썬에서 'K'개의 서로 다른 고유한 문자로 이루어진 길이 'N'의 부분 문자열을 찾아야 하는 경우가 있습니다. 이때는 문자열을 순회하면서 set 메서드를 활용해 각 부분 문자열 내 고유 문자의 개수를 확인하는 방식으로 문제를 해결할 수 있습니다.

예제 코드

다음은 위 방법을 구현한 예제입니다.

my_string = 'Pythonisfun'
print("The string is : ")
print(my_string)

my_substring = 2
my_chars = 2
my_result = []

for idx in range(0, len(my_string) - my_substring + 1):
   if (len(set(my_string[idx: idx + my_substring])) == my_chars):
      my_result.append(my_string[idx: idx + my_substring])
print("The resultant string is : ")
print(my_result)

실행 결과

The string is :
Pythonisfun
The resultant string is :
['Py', 'yt', 'th', 'ho', 'on', 'ni', 'is', 'sf', 'fu', 'un']

코드 설명

• 먼저 하나의 문자열을 정의하고 콘솔에 출력합니다.
• 부분 문자열의 길이(N)와 필요한 고유 문자의 개수(K)를 각각 변수로 지정합니다.
• 결과를 저장할 빈 리스트를 생성합니다.
• 문자열을 부분 문자열 길이만큼 슬라이딩하며 처음부터 끝까지 순회합니다. 인덱스 범위는 len(문자열) - N + 1로 설정하여 모든 경우를 포함합니다.
• 각 단계에서 set()을 사용해 해당 부분 문자열의 고유 문자 개수를 계산하고, 그 값이 K와 일치하면 결과 리스트에 추가합니다.
• 모든 조건을 만족하는 부분 문자열들이 담긴 최종 리스트를 콘솔에 출력합니다.

핵심 포인트

이 알고리즘의 핵심은 set 자료형의 중복 제거 특성입니다. 슬라이싱으로 추출한 부분 문자열을 집합으로 변환하면 자동으로 중복된 문자가 제거되므로, 집합의 크기(len)만 확인하면 해당 부분 문자열이 정확히 K개의 고유한 문자로 구성되어 있는지 손쉽게 판별할 수 있습니다. 시간 복잡도는 문자열 길이를 L이라 할 때 대략 O(L × N)이며, 슬라이딩 윈도우 기법을 응용해 더 효율적으로 개선할 수도 있습니다.