Longest Substring Without Repeating Characters 384

Question

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

Solution

我的方法：

1. 用一个index记录无重复的子字符串的左边界，用一个hashmap记录每个字符最靠右的位置。

2. 遍历数组，若hashmap中没有该字符，则在hashmap中添加该字符和其位置，若有，则将左边界更新为该字符之前位置，并将该字符更新为当前位置。

3. 更新左边界时，左边界只能向右移动，不能往左移，因此要判断更新位置和原来左边界的大小（如abccad）。

4. 若当前子字符串长度（当前字符位置减去左边界）比之前max大，则更新max。

九章的方法类似。

时间O(n)，空间O(n)。

代码如下：

我的方法：

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 max = 0;
        HashMap<Character, Integer> elem = new HashMap<Character, Integer>();
        int last = -1;
        for(int i = 0; i < s.length(); i++){
            if(!elem.containsKey(s.charAt(i))){
                elem.put(s.charAt(i), i);
            }else{
            //左边界只能往右移，不能往左移
                if(elem.get(s.charAt(i)) > last){
                    last = elem.get(s.charAt(i));
                }
                elem.put(s.charAt(i), i);
            }
            max = i - last > max? i - last : max;
        }

        return max;
    }
}