문제로 가기

문제

알파벳, 숫자, 기호, 그리고 공백으로 되어있는 문자열에서 중복된 문자가 들어가지않는 부분 문자열의 최댓값을 구하는것

Input: s = "abcabcbb"
Output: 3
abc 혹은 bca, cab가 최대 이므로 3

해결과정

생각

1. 가장 간단하게는 문자열의 처음부터 길이 1일때, 2일때 ......n일때까지 확인하다가 부분문자열에 중복되는 문자 출현시 그 길이가 최대일 경우 저장하고 다시 다음 문자부터 시작해서 확인
   -> 전체 문자 순회 n, 그 안에서 substring 늘리는것 n, 부분 문자열내부 탐색 n
   time complexity : O(n^3) 줄일 수 있을 것 같음

2. 각 문자들이 마지막으로 등장한 위치를 알고있다면 O(N)도 가능

3. Hashtable이용 이 안에 key값 존재하면 중복 문자 없으면 처음 나온 문자

필요 변수

1. cur_len -> 현재 길이 저장하는 변수
2. longest -> 가장 긴 substring의 길이
3. lib -> 각 문자들의 마지막 위치를 저장하는 Hashtable(파이썬 dictionary)

복잡도

문자열의 길이 N

공간 복잡도

문자열의 길이 만큼의 Hashtable -> N
O(N)

시간 복잡도

문자열 내의 모든 문자열을 한번씩 탐색하므로 N
O(N)
최악의 경우 dictionary내에서 탐색하는데 오래걸릴 경우 -> 거의 안나타남
W(N^2)

코드

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        length = len(s)
        #Hashtable storing last index of char 
        lib = {}
        
        #ans
        longest = 0
        
        #current length of substring
        cur_len = 0
        
        for i in range(length):
            cur_char = s[i]
            #if char occur before
            if cur_char in lib.keys():
                #for case that every char between is not repeated
                temp_len = i - lib[cur_char]
                #for case that char between is repeated
                cur_len = min(temp_len, cur_len+1)
            #which shown first
            else:
                cur_len += 1
            #store current index as last ocurrence
            lib[cur_char] = i
            #change longest if needed
            if cur_len > longest:
                longest = cur_len
        return longest

---

+슬라이딩 윈도우로 start와 end인덱스를 저장해서
end를 뒤로 밀면서 start와 같은 문자 나올시 start를 한칸 옮기는 방식으로 해결해도 같은 복잡도