Leetcode :: Longest Substring Without Repeating Characters

Problem

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.

Guess

• 문자별 갯수를 딕셔너리로 만들고,

• 투 포인터 알고리즘으로 구간 검사를 하면 되겠다.

Solution 1

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        mp = {x:0 for x in s}
        l,r = 0,0
        n = len(s)
        res = 0
        
        while r < n:
            mp[s[r]] += 1
            
            while mp[s[r]] > 1:
                mp[s[l]] -= 1
                l += 1
            
            res = max(res, r-l+1)
            r += 1
            
        return res

Solution 2

O(2n)을 O(n)으로 줄인 코드다.

중복 문자가 발견된 순간, 사이에 있던 다른 중복 문자를 포함해서 구할 수 있는 최대 길이는 이미 구해진 것이다. 고로 left index 를 right index가 있는 곳까지 하나씩 늘려봤자 해는 갱신되지 않는다.
이 점을 반영하여 Solution 1 코드를 최적화해보자.

• 맵에 문자 카운트가 아닌, 인덱스를 저장한다.
• 중복 문자 발견 시 left index를 중복 문자 바로 다음으로 옮긴다.

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        mp = {x:None for x in s}
        l,r = 0,0
        n = len(s)
        res = 0
        
        while r < n:
            idx = mp[s[r]]
            
            if idx != None and l<=idx<r:
                l = idx+1
            
            res = max(res, r-l+1)
            mp[s[r]] = r
            r += 1
        
        return res