파이썬으로 풀어보는 '반복 문자 없는 가장 긴 부분 문자열' 알고리즘

문제 개요

문자열이 하나 주어졌을 때, 반복되는 문자가 없는 가장 긴 부분 문자열(substring)의 길이를 찾는 것이 이번 문제의 목표입니다. 예를 들어 문자열이 "ABCABCBB"라고 한다면, 반복 문자가 없는 부분 문자열 중 가장 긴 것은 "ABC"이며 그 길이는 3이므로 결과값은 3이 됩니다.

접근 방법: 슬라이딩 윈도우

이 문제는 두 개의 포인터 i와 j를 활용하는 슬라이딩 윈도우(Sliding Window) 기법으로 효율적으로 해결할 수 있습니다. 여기에 해시맵(파이썬 딕셔너리)을 함께 사용하면 각 문자가 마지막으로 등장한 위치를 저장할 수 있어, 중복 문자 발생 시 윈도우의 시작 위치를 한 번에 건너뛰며 이동할 수 있습니다.

알고리즘의 구체적인 진행 과정은 다음과 같습니다.

i := 0, j := 0으로 초기화하고, 문자 정보를 저장할 맵(딕셔너리)을 하나 준비합니다.
정답을 담을 변수 ans := 0으로 초기화합니다.
j가 문자열 s의 길이보다 작은 동안 아래 과정을 반복합니다.
- s[j]가 맵에 존재하지 않거나, i가 map[s[j]]보다 크다면(현재 윈도우 내에 해당 문자가 없다면):
  - ans := max(ans, j - i + 1)
  - map[s[j]] := j로 마지막 등장 위치를 갱신
- 그렇지 않다면(현재 윈도우 안에 이미 해당 문자가 있다면):
  - i := map[s[j]] + 1로 윈도우의 시작점을 중복 문자 다음 위치로 이동
  - ans := max(ans, j - i + 1)
  - j를 1 감소시켜 현재 문자를 다시 검사
- 마지막으로 j를 1 증가시킵니다.
모든 반복이 끝나면 ans를 반환합니다.

파이썬 구현 예제

아래 코드를 통해 실제 구현 과정을 더 자세히 살펴보겠습니다.

class Solution(object):
   def lengthOfLongestSubstring(self, s):
      i =0
      j = 0
      d={}
      ans = 0
      while j < len(s):
         if s[j] not in d or i>d[s[j]]:
            ans = max(ans,(j-i+1))
            d[s[j]] = j
         else:
            i = d[s[j]]+1
            ans = max(ans,(j-i+1))
            j-=1
         #print(ans)
         j+=1
      return ans

ob1 = Solution()
print(ob1.lengthOfLongestSubstring("ABCABCBB"))

입력 및 출력 결과

입력:

"ABCABCBB"

출력:

마무리

이 방식은 각 문자를 최대 두 번만 방문하기 때문에 시간 복잡도가 O(n)으로 매우 효율적입니다. 브루트포스 방식처럼 모든 부분 문자열을 일일이 검사하는 대신, 딕셔너리에 마지막 등장 인덱스를 기록해 두면 중복을 만났을 때 윈도우 시작점을 한 번에 이동시킬 수 있어 성능이 크게 향상됩니다. 코딩 테스트에서 자주 출제되는 유형이므로 슬라이딩 윈도우 패턴과 함께 확실히 익혀두는 것이 좋습니다.