Leetcode::Longest Substring Without Repeating Characters

7263 ワード
python two pointer Sliding Window leetcode algorithm テキストリンク

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(2 n)をO(n)に減らすコード.
    重複文字が発見された瞬間,中間の他の重複文字を含めて求められる最大長さが求められた.したがって、左インデックスを右インデックスの場所に1つずつ追加すると、更新されません.
    この点について、Solution 1コードを最適化する.
  • マッピングには、文字数ではなくインデックスが格納されます.
  • の重複文字が見つかった場合、左のインデックスを重複文字の後に移動します.
    • 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
    Git Branch (local/remote)
    開発ログ3週目1日目