Leetcode 03.Longest Substring Without Repeating Characters

문제. 주어진 문자열에서 가장 긴 부분 문장열의 길이를 반환하는 코드를 작성하라

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

Longest Substring Without Repeating Characters - LeetCode

 

 

---

처음에 문제를 보고 저는 쉬운 문자열 문제인 줄 알았지만, 또 다시 해시문제임을 눈치채지 못한 ㅜㅠㅠㅠ 바보였습니다...

 

처음 풀이)

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        temp = []
        length = []
        
        for i in s:
            if i not in temp:
                temp.append(i)
            else:
                length.append(len(temp))
                temp = []
                temp.append(i)
                
        length.append(len(temp))      
        return max(length, default = 1) if s != "" else 0

처음에는 이런식으로 부분 문자열을 담을 temp와 길이를 담는 문자열을 형성해서 하나씩 뽑아서 중복되는게 나오면

중복되는 글자가 나오면 세는걸 멈추고 새로 부분 문자열을 만들고 길이를 세고, 마지막에 가장 긴 길이를 고르도록 했는데요

 

문제점 --> 여기서 문제점은 이렇게 순차적으로 지나가게 되면 중간 'dvdf'처럼 앞에서 부터 세면 2개 2개의 부분문자열이 나오지만 시작점이 두번째 글자부터 전개되는 vdf를 놓치게 됩니다. 그리고 전체를 다 세고 나서 가장 큰 길이값을 세는 연산이 다시 이루어지기 때문에 시간도 오래 걸리게 되는거죠

 

 

---

모범답변) 

역시 hash문제임을 눈치챈 고수님들은 enumerate과 인덱싱을 활용해서 푸셨는데요  

def lengthOfLongestSubstring(self, s):
        start = maxLength = 0
        usedChar = {}
        
        for i in range(len(s)):
            if s[i] in usedChar and start <= usedChar[s[i]]:
                start = usedChar[s[i]] + 1
            else:
                maxLength = max(maxLength, i - start + 1)

            usedChar[s[i]] = i

        return maxLength

부분 문자열이 시작되는 index --> start

부분문자열의 길이 비교를 위한 변수 -->  maxLength 

각 문자의 사용 여부 파악을 위한 변수 --> usedChar

 

이 코드에서는 for 문을 통해서 index 값을 뽑아주고,

1) if 조건문에서 문자열에서 사용되었는지 점검    2)  형성되는 문자열 index가 부분문자열의 시작점보다는 같거나 커야 함

위 조건을 충족할 시에  start 포인트를 다음 부분 문자열의 다음 위치로 이동

 

그 외의 경우에는 부분 문자열의 길이가 현재 최대 문자열의 길이와 새로 형성되는 문자열을 길이 중에 max값을 가지도록 합니다.

 

모범답변) 

    seen = {}
    left = 0
    curr_max = 0 
    for index, letter in enumerate(s):
        if letter in seen and left <= seen[letter]:
            left = seen[letter] + 1   
        else:
            curr_max = max(curr_max, index - left + 1)
        seen[letter] = index
        return curr_max

위와 같은 방식으로 풀이를 했는데요

차이점은 enumerate을 통해서 index을 도출하는 range(len())을 대체했다는 점!

 

모범답변) 

d, res, start = {}, 0, 0
        for i, ch in enumerate(s):
            if ch in d: start = max(start, d[ch]+1)
            res = max(res, i-start+1)                
            d[ch] = i
        return res

 

어떤 분은 이런식으로 첫 줄에 변수를 언패킹 하고

enumerate를 동일하게 사용했지만 start를 새로 찾은 동일한 부분 문자열의 시작점과 기존의 시작점 중에서 큰 값을 넣고

나머지는 동일하게 전개 되도록 했습니다!

 

 

---

정리해보자면 이 문제는 부분문자열 길이 ==> 끝나는 인덱스 - 시작되는 인덱스 +1 의 개념을 바탕으로

인덱싱을 hash를 통해 사용하고

if조건문을 통해서 이미 만들어진 부분열과 동일한 문자가 나오면 시작점을 기존 시작점에서 새로운 문자열 시작점으로 바꾸고, maxLength를 구할때는 기존에 있는 최대 문자열 길이와 새로 만들어진 길이 중에 큰 값으로 계속 업데이트 되도록 하는 로직이였습니다!!