[LeetCode] 3. Longest Substring Without Repeating Characters 파이썬 Medium

문제 해석:

문자열이 주어지면, 문자열내에 가장 긴 부분 문자열을 찾아야한다. 
반복 문자가 없어야 하는데, 그 말의 뜻은 연속이나 단어 단위로 반복이 되는게 아니다.
단지 이미 있었던 알파벳인지만 확인하면된다. 

문제 해설:

( 이해가 갑자기 잘안되서, 많이 해맸다.... )

슬라이딩 윈도우
1. 아스키코드로 문자의 개수를 저장한다.
2. 투포인터로 시작점 끝점을 지정하고, 와일문을 이용하여 끝점부터 이동시킨다.
3. 끝점을 이동시키기전에, 끝점에 해당하는 알파벳에 카운트를 올려준다.
4. 만약 새로 카운트를 올린 알파벳이 1보다 많다면, 줄어들때까지 와일문을 돌린다.
5. 줄이는 방법은 시작점 인덱스를 늘려주면서, 확인되는 문자들의 카운트들을 내려준다.
6. 그리고 시작점과 끝점을 계산하여 최대값을 구한다.

*********** 슬라이딩 윈도우 최적화 ************
1. 딕셔너리를 사용한다.
2. 시작점과 끝점 투포인터를 이용해, 알파뱃의 위치를 저장한다.
3. 끝점을 문자열의 처음부터 끝까지 반복하면서, 만약 이미 딕셔너리에 저장되어있다면 시작점을 갱신한다.
4. 현재 시작점과 문자가 발견된 위치 저장값이 있는 딕셔너리의 인덱스를 비교하여 큰값을 시작점으로 바꾼다.
5. 시작점과 끝점을 계산하여 최대 값을 구한다.
6. 끝점의 딕셔너리 값을 끝점위치 + 1로 갱신한다. ( 해당 문자는 속해있으면 안되기 때문 )

 

3. Longest Substring Without Repeating Characters

Given a string s, find the length of the longest substring without repeating characters.

 

Example 1:

Input: s = "abcabcbb" Output: 3 Explanation: The answer is "abc", with the length of 3.

Example 2:

Input: s = "bbbbb" Output: 1 Explanation: The answer is "b", with the length of 1.

Example 3:

Input: s = "pwwkew" Output: 3 Explanation: The answer is "wke", with the length of 3. Notice that the answer must be a substring, "pwke" is a subsequence and not a substring.

Example 4:

Input: s = "" Output: 0

 

Constraints:

• 0 <= s.length <= 5 * 104
• s consists of English letters, digits, symbols and spaces.

 

소스코드:

슬라이딩윈도우 O(n) = O(n^2)

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
    	start = 0
        end = 0
        res = 0
        cnt = [0] * 128
        while end < len(s):
            # end index going up
            endCh = s[end]
            # save ord index and plus point
            cnt[ord(endCh)] += 1
            # moving start and subject point
            while cnt[ord(endCh)] > 1:
                startCh = s[start]
                cnt[ord(startCh)] -= 1
                start += 1
            res = max(res, end - start + 1)
            end += 1

슬라이딩 윈도우 최적화 O(n)

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        cnt = dict()
        start = 0
        res = 0
        for end in range(len(s)):
            if s[end] in cnt:
                start = max(start, cnt[s[end]])
            res = max(res, end - start + 1)
            cnt[s[end]] = end + 1
        return res