LeetCode 3 - Longest Substring Without Repeating Characters

Given a string, find the length of the longest substring without repeating characters. 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.

 

Solution:

除了HashMap，我们还可以使用int[256]的数组来保存字符的索引。

public int lengthOfLongestSubstring(String s) {
    int n = s.length();
    if(n == 0) return 0;
    Map<Character, Integer> map = new HashMap<>();
    int start = 0, len = 0;
    for(int i=0; i<n; i++) {
        char c = s.charAt(i);
        if(map.containsKey(c) && map.get(c) >= start) {
            start = map.get(c) + 1; // test case: abba, when last 'a', we need to check start position
        }
        len = Math.max(len, i-start+1);
        map.put(c, i);
    }
    return len;
}