3. Longest Substring Without Repeating Characters

3. Longest Substring Without Repeating Characters (#1 Two pointer substring).java

// Two pointer solution: min/max substring templete
// Time: O(n), 2ms
// Space: O(1), 37.4mb
class Solution {
    public int lengthOfLongestSubstring(String s) {
        // char table that keeps track of characters we have met
        int[] table = new int[128];
        int count = 0; // Count of unique char
        
        int begin = 0, end = 0, maxLen = 0; // Window is [begin, end)
        while(end < s.length()) {
            // Expand window to the right
            if(table[s.charAt(end++)]++ == 0) {
                // table[] was 0 before, this is the first char in the table
                count++;
            }
                
            // Shrink the window from left side until we don't have repeating char
            while(end - begin > count) {
                // Shrink the window
                if(table[s.charAt(begin++)]-- == 1) {
                    // If we delete the last char in the window
                    count--;
                }
            }
            
            // Update length when we don't have repeating char
            if(end - begin > maxLen) {
                maxLen = end - begin;
            }
        }
        
        return maxLen;
    }
}

3. Longest Substring Without Repeating Characters (#1.0 Two pointer substring).java

class Solution {
    public int lengthOfLongestSubstring(String s) {
        int[] table = new int[128];
        for(int i = 0; i < table.length; i++) table[i] = -1;
        int begin = 0, end = 0, ans = 0;
        while(end < s.length()) {
            //Move the end pointer to make it invalid
            while(end < s.length() && table[s.charAt(end)] == -1) {
                table[s.charAt(end++)] = end;
                ans = Math.max(ans, end - begin);
                //Note: We need to update the ans more often if we move end more than 1 step in the outer while loop
            }
            //Move the begin pointer directly to make it valid
            if(end < s.length()) {
                if(table[s.charAt(end)] != -1) {
                    while(begin < table[s.charAt(end)] + 1)
                        table[s.charAt(begin++)] = -1;
                }
                table[s.charAt(end++)] = end;
            }
            //Now [begin, end) is a valid solution
            ans = Math.max(ans, end - begin);
        }
        return ans;
    }
}

3. Longest Substring Without Repeating Characters (#1.1 Two pointer).java

//Solution #1: Two pointers (Sliding window)
//Difference between two pointers and iteratoin: Just remove the first one when meet duplicates, instead of remove all.
class Solution {//abcad
    public int lengthOfLongestSubstring(String s) {
        int i = 0, j = 0, n = s.length(), ans = 0;
        Set<Character> set = new HashSet<>();
        while(i < n && j < n) {
            if(!set.add(s.charAt(j))) {
                set.remove(s.charAt(i++));
            } else {
                ans = Math.max(ans, j - i + 1);
                j++;
            }
        }
        return ans;
    }
}

3. Longest Substring Without Repeating Characters (#1.2 Two pointer).java

//Solution #2: Revised Two pointers
//Move more steps when meet duplicates: use a hash table to save the index
class Solution {
    public int lengthOfLongestSubstring(String s) {
        int i = 0, j = 0, n = s.length(), ans = 0;
        Map<Character, Integer> map = new HashMap<>();  //Save the index in the map
        for(i = 0, j = 0; j < n; j++) {
            if(map.containsKey(s.charAt(j))) {
                i = Math.max(i, map.get(s.charAt(j)) + 1);  //Move i untill there is no overlap
            }
            map.put(s.charAt(j), j);
            ans = Math.max(ans, j - i + 1);  //tmmzuxt
        }
        return ans;
    }
}

3. Longest Substring Without Repeating Characters (#1.3 Two pointer).java

//Solution #3: Revised Two pointers
//Move more steps when meet duplicates: use a table to save the index when character range is fixed
class Solution {
    public int lengthOfLongestSubstring(String s) {
        int i = 0, j = 0, n = s.length(), ans = 0;
        int[] table = new int[256];  //Save the index in the table (range is fixed) (default value: 0)
        for(i = 0, j = 0; j < n; j++) {
            i = Math.max(i, table[s.charAt(j)]);  //Move i untill there is no overlap
            table[s.charAt(j)] = j + 1;
            ans = Math.max(ans, j - i + 1);  //tmmzuxt
        }
        return ans;
    }
}