LeetCode 3. Longest Substring Without Repeating Characters

原題鏈接在這里：https://leetcode.com/problems/longest-substring-without-repeating-characters/

題目：

Given a string, find the length of the longest substring without repeating characters. For example, the longest substring without repeating letters for "abcabcbb" is "abc", which the length is 3. For "bbbbb" the longest substring is "b", with the length of 1.

題解：

快慢指針維護substring的方法在Minimum Window Substring里有總結.

窗口[walker,runner]. walker, runner都是向右移，維護map, 用來存儲掃過char的frequency. 首先右側窗口runner在前跑，掃過char的frequency 加一. 直到遇到frequency已經大于零, 說明前面有相同元素, runner停下移動walker. walker 掃過char的frequency減一, 直到把frequency大于1的那個char掃過.

Time Complexity: O(n). n = s.length().

Space: O(1). 256 map size.

AC Java:

public class Solution {
    public int lengthOfLongestSubstring(String s) {
        int res = 0;
        int [] map = new int[256];
        int count = 0;
        int walker = 0;
        int runner = 0;
        
        while(runner < s.length()){
            if(map[s.charAt(runner++)]++ > 0){
                count++;
            }
            while(count > 0){
                if(map[s.charAt(walker++)]-- > 1){
                    count--;
                }
            }
            res = Math.max(res, runner-walker);
        }
        return res;
    }
}

上面的方法會跑2*n, 可以只跑n. 需用HashMap來記錄每個char和對應index的關系.

遇到repeating char時walker直接走到之前出現這個char的后一位即可.

Time Complexity: O(n). Space: O(n).

AC Java:

public class Solution {
    public int lengthOfLongestSubstring(String s) {
        int res = 0;
        HashMap<Character, Integer> hm = new HashMap<Character, Integer>();
        for(int walker = 0, runner = 0; runner<s.length(); runner++){
            char c = s.charAt(runner);
            if(hm.containsKey(c)){
                walker = Math.max(walker, hm.get(c));
            }
            res = Math.max(res, runner-walker+1);
            hm.put(c, runner+1);
        }
        return res;
    }
}

?跟上Longest Substring with At Most Two Distinct Characters