3. Longest Substring Without Repeating Characters

Loading...LeetCode

Python

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        maxLen = 0
        
        i, j = 0, 0
        while j < len(s):
            # 更新条件：新进元素在window里重复
            while s[j] in s[i:j]:
                maxLen = max(maxLen, j-i)
                i += 1
                
            j += 1
        maxLen = max(maxLen, j-i)
        return maxLen

Java

class Solution {
    public int lengthOfLongestSubstring(String s) {
        int res = 0;
        HashSet<Character> window = new HashSet<Character>();
        int l = 0, r = 0;
        char[] arr = s.toCharArray();
        while (r<arr.length) {
            char curr = arr[r];
            while (window.contains(curr)) {
                window.remove(arr[l]);
                l++;
            }
            window.add(curr);
            res = Math.max(res, window.size());
            r++;
        }
        return res;
        
    }
}

12/30/2020 Update

重写的时候第一反应用了 index 函数，好处是更新一步到位，在Python中不用反复切片string。但这个写法需要维护 window，worse case 的时间复杂度是O(N).

P.S. 最后多的一次 max 比较确实很容易忘掉。

Python

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        res, window = 0, ""
        for ch in s:
            if ch in window:
                res = max(res, len(window))
                window = window[window.index(ch)+1:] + ch
            else:
                window += ch
        res = max(res, len(window))
        return res

class Solution {
    public int lengthOfLongestSubstring(String s) {
        int res = 0;
        StringBuilder window = new StringBuilder();
        
        for (char c: s.toCharArray()) {
            String ch = Character.toString(c);
            if (window.toString().contains(ch)) {
                res = Math.max(res, window.length());
                window = new StringBuilder(window.substring(window.indexOf(ch)+1, window.length()));
            }
            
            window.append(ch);
            
        }
        
        res = Math.max(res, window.length());
        return res;
    }
}