📕문제

[LeetCode] 3. Longest Substring Without Repeating Characters

문제 설명

문자열 s에서 중복된 문자를 포함하지 않는 부분 문자열의 최대 길이를 구하는 문제다.

---

📝풀이

투포인터

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        if len(s) == 0:
            return 0
        
        left, right = 0, 0
        chars, result = set(), set()
        while right < len(s):
            if s[right] not in chars:
                chars.add(s[right])
                right += 1
            else:
                chars.remove(s[left])
                left += 1
            result.add(right-left)
        return max(result)

변수 설명

• left: 부분 문자열의 시작 인덱스
• right: 부분 문자열의 끝 인덱스
• chars: 검사중인 부분 문자열에 존재하는 문자를 저장하기 위한 set
• result: 검사한 각 부분 문자열의 길이를 저장하기 위한 set

코드 설명

• left와 right를 0으로 설정 후 투포인터 시작.
• chars안에 right이 가리키는 문자가 없는 경우: chars에 추가 후 오른쪽 포인터를 한 칸 이동한다.
• chars안에 right이 가리키는 문자가 있는 경우: chars에서 삭제 후 왼쪽 포인터를 한 칸 이동한다.
• 부분 문자열 검사가 끝나면 해당 부분 문자열의 길이를 result에 추가한다.
• 문자열 끝까지 검사를 마친 후 result에서 가장 큰 값을 반환한다.

chars와 nums가 집합(set)인 이유!
반복문을 진행하며 값 포함 여부 검사와 데이터를 추가, 제거하는 연산이 많았기 때문에 모든 연산에 대해 시간복잡도가 $O(1)$인 집합(set)을 선택했다.