[LintCode] 384 Longest Substring Without Repeating Characters 解题报告

Description
Given a string, find the length of the longest substring without repeating characters.



Example
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.



Challenge
O(n) time


思路 (这个答案不对。。。待更新。。。)
这是一道“前向型”指针的题。我们维护两个指针i和j从头往下走。
同时，我们维护一个hash table。
我们知道如果从index a走到index b如果都没有重复的，那么index a + 1加到index b肯定也不会有重复。这样我们就可以避免重复计算从index a + 1到index b这段。
如果我们沿着j走，发现和i没有重复，那么我们把j这个位置上的字符放进hash table。并且j++。反之如果i和j位置上对应的字符重复了，说明i + 1到j这个区间没有重复的。我们只要把i这个位置的字符从hash table里删除，并且i++，j从当前位置接着往下走。


Code

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[] check = new int[256];
        int i = 0;
        int j = 0;
        int max = Integer.MIN_VALUE;
        for (i = 0; i < s.length(); i++) {
            while (j < s.length()) {
                if (check[s.charAt(j)] != 1) {
                    check[s.charAt(j)]++;
                    j++;
                    max = Math.max(max, j - i);
                }
                else {
                    check[s.charAt(i)]--;
                    break;
                }
            }
        }
        if (max == Integer.MIN_VALUE) {
            return 1;
        }
        return max;
    }
}