30. Longest Substring Without Repeating Characters

🎯 leetcode - 3. Longest Substring Without Repeating Characters

---

🤔 나의 풀이

📌 문제

- 파이썬 알고리즘 인터뷰 30번 문제
- 중복 문자가 없는 가장 긴 부분(이어진) 문자열의 길이를 리턴하라.

📌 날짜

2020.02.01

📌 시도 횟수

2 try

💡 Code

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        count = max_count = 0
        word_dict = []
        for word in s:
             if word in word_dict:
                if count >= max_count:
                    max_count = count

                check_idx = word_dict.index(word)
                word_dict = word_dict[check_idx + 1 :]
                count = len(word_dict)

            word_dict.append(word)
            count += 1
        return count if count > max_count else max_count

+ count 대신 len(word_dict) 사용

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        max_count = 0
        word_dict = []
        for word in s:
            if word in word_dict:
                if len(word_dict) >= max_count:
                    max_count = len(word_dict)

                check_idx = word_dict.index(word)
                word_dict = word_dict[check_idx + 1 :]

            word_dict.append(word)
        return len(word_dict) if len(word_dict) > max_count else max_count

💡 문제 해결 방법

- 위의 방법대로 풀었다.

- 각 문자를 list에 넣다가 중복이 발생하면...
> 현재까지의 count와 max_count를 비교하여 max_count를 갱신한다.
> list에서 중복된 값까지의 부분을 삭제하여 갱신한다.
> 갱신한 list의 길이에 맞게 현재 count를 다시 갱신한다.

💡 새롭게 알게 된 점

-

❌ (한번에 맞추지 못한 경우) 오답의 원인

- 처음에 중복 발생 시 count = 0으로 초기화 했더니 일부 테스트에서만 통과했다.
→ [a, b, c, a, e, f] 같은 케이스들은 통과하지 못했다.

---

😉 다른 풀이

📌 하나. 슬라이딩 윈도우

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

        return max_len

💡 문제 해결 방법

• 아래 그림의 경우 list로 나타냈지만 위 코드에서는 이를 딕셔너리 dict[char] = index로 구현함

- 충돌(중복 문자 발생)이 일어나면 start의 인덱스를 (중복 문자 인덱스 + 1)으로 갱신한다.
- start ~ 현재 index까지의 길이와 max_len을 비교하여 max_len을 갱신한다.

💡 새롭게 알게 된 점

- 슬라이딩 윈도우(Sliding Window) 알고리즘에 대해 알게 되었다.

🌵 투포인터와 슬라이딩 윈도우(Sliding Window)?

투포인터

- 주로 정렬된 배열을 대상으로 한다.
- 윈도우의 사이즈가 가변적이다.
- 두 포인터가 양방향으로 자유롭게 이동 가능하다.

슬라이딩 윈도우(Sliding Window)

- 윈도우의 사이즈가 고정되어 있다.
- 정렬되어 있지 않은 배열에도 사용 가능하다.
- 두 포인터는 좌/우 한쪽 방향으로만 이동한다.
- 배열이나 리스트의 요소의 일정 범위의 값을 비교할때 사용하면 유용한 알고리즘이다.

---