Python으로 동일한 두 문자 사이에서 가장 긴 부분 문자열 찾기

문자열 s가 주어졌을 때, 서로 같은 두 문자 사이에 위치한 부분 문자열 중 가장 긴 것의 길이를 구하는 문제입니다. 단, 양 끝에 있는 두 문자 자체는 길이 계산에서 제외하며, 조건을 만족하는 부분 문자열이 존재하지 않으면 -1을 반환해야 합니다.

예를 들어 입력이 s = "level"이라면 출력은 3이 됩니다. 첫 번째 'l'(인덱스 0)과 마지막 'l'(인덱스 4) 사이의 부분 문자열은 "eve"이고, 그 길이가 3이기 때문입니다.

문제 해결 접근 방식

핵심 아이디어는 간단합니다. 각 문자가 처음 등장한 인덱스와 마지막에 등장한 인덱스의 차이가 곧 해당 문자 기준으로 만들 수 있는 최대 부분 문자열의 길이가 됩니다. 이를 위해 다음 단계를 따릅니다.

• memo := 새로운 딕셔너리(맵) 생성
• i를 0부터 s의 길이 - 1까지 반복:
  • s[i]가 memo에 이미 존재하면 → memo[s[i]] 리스트의 끝에 i를 추가
  • 존재하지 않으면 → memo[s[i]] := i 하나만 담긴 리스트로 초기화
• best := 0으로 초기화
• memo의 각 키에 대해:
  • best := max(best, memo[key]의 마지막 원소 − 첫 번째 원소)
• best − 1을 반환

여기서 best - 1을 반환하는 이유는 다음과 같습니다. 어떤 문자가 두 번 이상 등장했다면 인덱스 차이는 항상 1 이상이므로 결과는 0 이상이 되고, 모든 문자가 고유하다면 best는 0 그대로 유지되어 함수가 -1을 반환하게 됩니다.

Python 예제 코드

def solve(s):
    memo = {}
    for i in range(len(s)):
        if s[i] in memo:
            memo[s[i]].append(i)
        else:
            memo[s[i]] = [i]

    best = 0
    for key in memo:
        best = max(best, memo[key][-1] - memo[key][0])
    return best - 1

s = "level"
print(solve(s))

입력

"level"

출력

3

시간 및 공간 복잡도

시간 복잡도: O(n) — 문자열을 한 번만 순회하여 각 문자의 인덱스를 기록하고, 딕셔너리를 한 번 더 순회하므로 전체적으로 선형 시간이 소요됩니다.

공간 복잡도: O(n) — 최악의 경우 모든 문자가 고유할 때 각 인덱스를 저장하기 위해 문자열 길이에 비례하는 메모리가 필요합니다.