leetcode解题: Longest Substring Without Repeating Characters (3)

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

Examples:

Given “abcabcbb”, the answer is “abc”, which the length is 3.

Given “bbbbb”, the answer is “b”, with the length of 1.

Given “pwwkew”, the answer is “wke”, with the length of 3. Note that the answer must be a substring, “pwke” is a subsequence and not a substring.

解法1：

这个答案对我的启发比较大，主要可以用于一类题目。
思路是用一个hashtable维护出现过的字母的位置，只存储上一次出现过的位置。
那么如果遇到还未出现过的字符则直接向前进，如果遇到出现过的字符那么需要比较当前的substring的长度和max。
同时，需要移动left指针，因为从left开始到right部分已经不符合要求了。left需要移动到上一次出现的位置+1.
注意这里有个坑：因为可能出现上一次的位置比现在left的位置还好往后，要保证left只进不退，只能用left = Math.max(left, last_pos)来保证。
还有一个坑，就是在最后一步还需要判断max和当前right - left的大小的比较。
Java

public class Solution {
    public int lengthOfLongestSubstring(String s) {
        
        int[] table = new int[256];
        Arrays.fill(table, -1);
        
        int left = 0, right = 0;
        int max = 0;
        while (right < s.length()) {
            int current_char = (int)s.charAt(right);
            int last_pos = table[current_char];
            if (last_pos != -1) {
                max = Math.max(right - left, max);
                // move left pointer
                left = Math.max(left, table[current_char] + 1);
                table[current_char] = right;
            } else {
                table[current_char] = right;
            }
            ++right;
        }
        
        return Math.max(max, right - left);
        
    }
}