3. Longest Substring Without Repeating Characters

LintCode超靠谱讲解

五刷 06/2022

Version #2 Sliding Window Optimized

还是写了以前一直犯的错误，就是如果lastIndex是小于当前的start的时候，我们是不会退回去的，因为这表示最后一个重复的character并不在我们的sliding window里面

所以要对lastIndex 和 start 取max

Time O(N)

Space O(M) - size of the charset

Runtime: 8 ms, faster than 76.00% of Java online submissions for Longest Substring Without Repeating Characters.

Memory Usage: 44.9 MB, less than 51.67% of Java online submissions for Longest Substring Without Repeating Characters.

class Solution {

    public int lengthOfLongestSubstring(String s) {

        int max = 0;

        Map<Character, Integer> lastIndex = new HashMap<>();

        int start = 0;

        for (int end = 0; end < s.length(); end++) {

            char c = s.charAt(end);

            int li = lastIndex.getOrDefault(c, -1);

            if (li != -1) {

                start = Math.max(start, li + 1);

            }

            lastIndex.put(c, end);

            max = Math.max(max, end - start + 1);

        }

        return max;

    }

}

Version #1
14.92%
public class Solution {
    public int lengthOfLongestSubstring(String s) {
        if (s == null || s.length() == 0) return 0;
        int slow = 0, fast = 0;
        int maxLength = 0;
        Set<Character> set = new HashSet<>();
        while (fast < s.length() && slow <= fast) {
            //System.out.println(s.charAt(slow) + " " + s.charAt(fast));
            if (set.contains(s.charAt(fast))) {
                set.remove(s.charAt(slow++));
            } else {
                set.add(s.charAt(fast++));
                maxLength = Math.max(maxLength, fast - slow);
            }
        }
        return maxLength;
    }
}

Commonly used tables are:

• int[26] for Letters 'a' - 'z' or 'A' - 'Z'
• int[128] for ASCII
• int[256] for Extended ASCII

Version #2 hash to index
 Instead of using a set to tell if a character exists or not, we could define a mapping of the characters to its index. Then we can skip the characters immediately when we found a repeated character.

 97.36%
public class Solution {
    public int lengthOfLongestSubstring(String s) {
        if (s == null || s.length() == 0) return 0;
        int maxLength = 0;
        int slow = 0, fast = 0;
        int[] hash = new int[128];
        for (slow = 0, fast = 0; fast < s.length(); fast++) {
            //Valid subString [slow, fast]
            slow = Math.max(slow, hash[s.charAt(fast)]);
            maxLength = Math.max(maxLength, fast - slow + 1);
            hash[s.charAt(fast)] = fast + 1;
        }
        return maxLength;
    }
}

二刷自己又写了一遍
总的来说思路比较清楚但是犯了一个特别愚蠢的问题就是在用lastIndex更新slow pointer的时候没有check slow pointer是不是在lastIndex之前。如果slow pointer已经走过了lastIndex，就会出错。上面一刷的解法直接取了max也是比较简洁的
public class Solution {
    /**
     * @param s: a string
     * @return: an integer
     */
    public int lengthOfLongestSubstring(String s) {
        // write your code here
        if (s == null || s.length() == 0) return 0;
        int[] lastIndex = new int[128]; //capacity of ASCII character set
        int slow = 0, fast = 0;
        char currIndex;
        int maxLength = 0;
        for (fast = 0; fast < s.length(); fast++) {
            currIndex = s.charAt(fast);
            if (lastIndex[currIndex] != 0 && lastIndex[currIndex] > slow) {
                slow = lastIndex[currIndex];
                //System.out.println("slow");
            }
            lastIndex[currIndex] = fast + 1;
            maxLength = Math.max(maxLength, fast - slow + 1);
            //System.out.println(currIndex + " " + lastIndex[currIndex] + " max:" + maxLength);
        }
        return maxLength;
    }
}

三刷
HashMap -> lastOccurance
83.66 %
class Solution {
    public int lengthOfLongestSubstring(String s) {
        if (s == null || s.length() == 0) {
            return 0;
        }
        // key -> current char, value -> last occurance of current char
        Map<Character, Integer> map = new HashMap<>();
        int max = 0;
        int left = 0;
        int right = 0;
        // [left, right] valid string
        for (right = 0; right < s.length(); right++) {
            char c = s.charAt(right);
            int lastOccurance = map.getOrDefault(c, right);
            if (lastOccurance != right) {
                left = Math.max(left, lastOccurance + 1);
            }
            map.put(c, right);
            max = Math.max(max, right - left + 1);
        }
        return max;
    }
}

四刷

Two pointer

Runtime: 70 ms, faster than 92.46% of Java online submissions for Making A Large Island.

Memory Usage: 77.9 MB, less than 40.19% of Java online submissions for Making A Large Island.

class Solution {

    public int lengthOfLongestSubstring(String s) {

        int max = 0;

        // p  q

        // |  | 

        // abcabcbb

        

        boolean[] visited = new boolean[256];

        int p = -1;

        for (int q = 0; q < s.length(); q++) {

            char c = s.charAt(q);

            while (visited[c]) {

                p++;

                visited[s.charAt(p)] = false;

            }

            visited[s.charAt(q)] = true;

            max = Math.max(max, q - p);

        }

        return max;

    }

}