[해시 테이블] 중복 문자 없는 가장 긴 부분 문자열

3 | Longest Substring Without Repeating Characters
https://leetcode.com/problems/longest-substring-without-repeating-characters/

 

 

 

 

 

작성 코드

 

접근 방법

 

1. for 문을 두 번 돌면서 해결 (시작 값, 끝 값)
2. 임시 저장 변수 만들어줘서 끝 값이 중복인지 아닌지 확인
3. 중복이면 break, 중복이 아니면 임시 저장 변수에 더해줌
4. 임시 저장 변수의 len 을 append
5. 가장 큰 max 값 append

 

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        subs = []
        for i in range(len(s)):
            temp = s[i]
            for j in range(i + 1, len(s)):
                if s[j] in temp:
                    break
                temp += s[j]
            subs.append(len(temp))
        return max(subs) if subs else 0

 

• 접근 방법대로 코드를 작성했는데, s가 공백일 경우를 생각을 못해서 에러가 떴음

 

 

이상 코드

 

슬라이딩 윈도우와 투 포인터로 사이즈 조절

 

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        used = {}
        max_length = start = 0
        for index, char in enumerate(s):
            if char in used and start <= used[char]:
                start = used[char] + 1
            else:  
                max_length = max(max_length, index - start + 1)

            used[char] = index

        return max_length

 

• 문자열 s에 대해 for 반복문을 돌며 used[char]에 현재 인덱스 값 저장
• char in used 경우에는 중복된 문자열임, start <= used[char] // 두 경우가 되면 start 값을 used[char] + 1 값으로 설정