[Leetcode] 3. Longest Substring Without Repeating Characters

✅ 문제 - 중복 문자가 없는 가장 긴 부분 문자열

 

주어진 문자열에서 중복 문자가 없는 문자열의 길이를 구하는 문제

 

 

---

 

✅ 풀이

💡 슬라이딩 윈도우와 투 포인터 이용
1. char_list에 현재 담긴 문자의 위치를 지정해서 범위를 설정
2. 투 포인터(start, index) 이용하여 그 차이로 max값 구하기
3. char_list에 해당하는 문자가 있는지 확인하여
  3-1) 중복되는 문자가 없으면 현재범위에 추가
  3-2) 기존에 있는 문자일 경우는 index를 통해 위치만 갱신시켜 현재 위치 범위를 옮겨주면서 start 포인터 오른쪽으로 이동

 

현재 문자열의 범위를 해시 테이블 구조를 이용해 인덱스를 찍고 범위설정을 하는 것이 놀라웠다.

그저 문자열로 for문만 돌릴 궁리를 했었는데, 다른 사람들의 풀이와 해설을 보면서 알고리즘의 세계는 끝이 없구나 느꼈음

 

✅ 전체 코드

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:

        if len(s) == 1:
            return len(s)

        # 현재 구간의 위치 인덱스를 담는 테이블
        char_list = {}

        max_len = 0 # 문자열 길이
        start = 0  # 시작 지점

        for index, char in enumerate(s):  # 인덱스를 붙여 for문 돌림

            # 현재 문자가 중복문자이면서 현재 범위에 있으면 start 위치를 다음으로 옮김
            if char in char_list and start <= char_list[char]:
                start = char_list[char] + 1

            # char_list에 담긴 문자가 아닌 경우(아직 겹친 문자가 없음)
            # 최대 길이
            # 를 구하기 위해 max_len값을 올림
            else:
                # 현재 max_len와 새로 구한 문자열 길이 중 큰 값을 max_len으로 함
                max_len = max(max_len, index - start + 1)

            # 현재 문자의 인덱스를 char_list에 담음
            char_list[char] = index

        return max_len

 

 

이 문제 역시 아래와 같이 그려가면서 이해해봤다.