[Leetcode] 3. Longest Substring Without Repeating Characters (python)

#1.  문제

 

https://leetcode.com/problems/longest-substring-without-repeating-characters/

Longest Substring Without Repeating Characters - LeetCode

 

 

주어진 문자열 s에서 중복이 없이 만들 수 있는 가장 긴 substring을 찾는 문제

(substring이기 때문에 기본적으로 문자열 s의 이어지는 순서를 적용한다. 즉, 중간의 중복되는 문자열만 빼고 이어버린다면 substring이 아니다.)

 

# input
s = "anviaj"

# output
Output: 2

# explanation
"nviaj" 길이 5의 substring을 만들 수 있다.

 

---

#2.  풀이

 

 

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        sub = ""
        max_len = 0

        for i in range(len(s)):
            char = s[i]
            if char in sub:
                duplicated_idx = sub.index(char)
                sub = sub[duplicated_idx + 1 :] + char
            else:
                sub += char

            max_len = max(max_len, len(sub))

        return max_len

 

문자열 s의 원소를 차례대로 더해가면서 substring을 만들어준다.

더하려는 문자가 이미 substring안에 있다면 substring안의 중복 문자열까지 버린 후 이후 인덱스 요소부터 다시 substring을 만들기 시작한다.반복마다 가장 긴 substring의 길이를 갱신해준다.

 

in 연산과 index 함수의 연산은 기본적으로 O(n)이다.중복문자가 있다면 substring의 길이는 짧게 갱신되기 때문에 전체 풀이 역시 O(n)으로 처리 가능해보인다.

 

미리 해시맵을 통해 요소와 인덱스를 매핑한다면 좀 더 효율적으로 보인다.