3. Longest Substring Without Repeating Characters

Question

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

Solution 1

滑动窗口加数组统计。
用一个数组bin[]记录各个字符的访问情况。（数组尺寸由字符串的总数决定）

当指针j第一次遍历到一个字符时，如果该字符对应的位置为0，则将其设置为1。
否则对前面的i指针进行遍历，并将i经过的位置重新设置为0。如果i的字符与当前j字符相等，则将bin[index]设置为0，计算当前的长度j-i并更新最大值best。

Code

class Solution {
    public int lengthOfLongestSubstring(String s) {
        int best = 0, i = 0, j = 0;
        char[] word = s.toCharArray();
        int[] bin = new int[128];
        while(j < s.length()){
            int index = word[j] - ' ';
            if(bin[index] == 0){
                bin[index] = 1;
                j++;
            }
            else{
                while(i < j){
                    int temp = word[i] - ' ';
                    if(temp == index && bin[index] == 1){
                        bin[index] = 0;
                        best = Math.max(best, j - i);
                        i++;
                        break;
                    }
                    bin[temp] = 0;
                    i++;
                }
            }
            best = Math.max(best, j - i);
        }
        return best;
    }
}

Solution 2

滑动窗口，哈希表记录访问过的字符的元素。
如果重复，则放弃前一个重复的字符，更新左指针。
注意：只有在新指针大于现有指针时才更新！

Code

class Solution {
    public int lengthOfLongestSubstring(String s) {
        int best = 0;
        int i = 0;
        int j = 0;
        
        HashMap<Character, Integer> map = new HashMap<Character, Integer>();
        
        while ( j < s.length() ){
            char curChar = s.charAt(j);
            if ( !map.containsKey(curChar) ){
                map.put( curChar, j );
            }
            else{
                if ( map.get(curChar) + 1 > i){
                    i = map.get(curChar) + 1;
                }

                map.put( curChar, j );
            }
            
            if ((j - i + 1) > best){
                best = (j - i + 1);
            }
            j++;
        }
        return best;
    }
}