파이썬으로 문자열의 고유한 부분 수열 개수 세기

문자열 s가 주어졌을 때, 이 문자열에서 만들 수 있는 서로 다른(고유한) 부분 수열의 개수를 세는 프로그램을 작성해 보겠습니다. 답이 너무 커질 수 있으므로, 결과는 10^9 + 7로 나눈 나머지를 반환합니다.

예를 들어 입력이 s = "bab"라면 출력은 6입니다. 만들 수 있는 서로 다른 부분 수열은 다음과 같습니다.

길이 1: "b", "a"
길이 2: "bb", "ba", "ab"
길이 3: "bab"

즉, 총 6개의 고유한 부분 수열이 존재합니다.

접근 방법: 동적 계획법(DP)

이 문제는 동적 계획법을 이용해 효율적으로 해결할 수 있습니다. 핵심 아이디어는 각 위치에서 끝나는 부분 수열의 개수를 누적하는 것입니다.

다음 단계로 진행합니다.

dp 배열을 문자열 s와 같은 크기로 만들고 0으로 초기화합니다.
모듈러 값 m := 10^9 + 7을 설정합니다.
문자열의 각 인덱스 i와 문자 char에 대해 다음을 수행합니다.
- ind: 현재 인덱스 i보다 앞쪽 범위에서 char가 마지막으로 등장한 위치 (없으면 -1)
- ind == -1(처음 등장하는 문자)이면 dp[i] = (dp[0]부터 dp[i-1]까지의 합 + 1) mod m
- 그렇지 않으면(중복 방지를 위해 이전 등장 위치 이후 구간만 사용) dp[i] = (dp[ind]부터 dp[i-1]까지의 합) mod m
마지막으로 dp 배열 전체의 합을 m으로 나눈 나머지를 반환합니다.

여기서 중복 제거가 핵심입니다. 어떤 문자가 이미 앞에서 등장했다면, 그 이전 등장 위치 이전까지의 결과를 다시 더하면 같은 부분 수열이 중복 계산되므로, 마지막 등장 지점 이후 구간만 더해 줍니다.

구현 코드

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

def solve(s):
    dp, m = [0] * len(s), 10**9 + 7
    for i, char in enumerate(s):
        ind = s.rfind(char, 0, i)
        if ind == -1:
            dp[i] = (1 + sum(dp[:i])) % m
        else:
            dp[i] = sum(dp[ind:i]) % m
    return sum(dp) % m

s = "bab"
print(solve(s))

실행 결과

solve("abcd")를 호출하면 모든 문자가 처음 등장하므로 dp = [1, 2, 4, 8]이 되어 결과는 15가 됩니다. 즉, 서로 다른 문자로만 구성된 길이 n의 문자열은 2^n − 1개의 비어 있지 않은 부분 수열을 가집니다.

시간 복잡도

위 구현은 각 인덱스마다 구간합을 계산하기 위해 O(n)의 연산을 수행하므로, 전체 시간 복잡도는 O(n²)입니다. 누적합(prefix sum)을 유지하도록 최적화하면 O(n)까지 개선할 수 있습니다.