最大子字符串，哈希，O(n)

Description

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.

Solution

1. 用max表示到目前为止的最大子字符串的长度，用tmp记录当前字符结尾的最大子字符串长度，用hash[arr[i]]表示第i个字符arr[i]最后一次出现的索引加1（ 考虑到hash数组初始值均为0），例如对于"abcbacbb"，当索引(从0开始)为2时，char=‘c’, max = 3, tmp = 3（对应abc）. 当索引为3时，char='b', max = 3, tmp = 2（对应cb）;

2. 每次迭代当索引为index时，判断当前字符是否已经出现过，如果未出现过，则tmp = tmp + 1， 如果已出现过，则tmp = min(tmp + 1, index + 1 - hash[arr[i]]);

3. 每次迭代索引为index时，更新hash，hash[arr[index]] = index + 1（考虑到hash数组初始值均为0）;

Code

public int maxSubstring(String s) { char[] arr = s.toCharArray(); // 'hash' saves the index of character at the last seen int[] hash = new int[255]; int max = 0; // 'tmp' is the length of the longest subString with the end of 'arr[i]' at the time for (int i = 0, tmp = 0; i < s.length(); i++) { tmp = Math.min(i + 1 - hash[arr[i]], tmp + 1); max = Math.max(tmp, max); hash[arr[i]] = i + 1; } return max; }