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.

题目要求很简单，给定一个字符串，找到一个不包含重复元素的最长字符串。
我们可以用哈希表来处理，key中存放字符，value存放相应字符的下标，max记录不包含重复元素的最长字符串的长度。从第一个字符开始，如果当前字符在哈希表中，那么就更新遍历的开始位置，同时维护max；如果不在哈希表中，就将当前元素记录到哈希表中。代码如下：

public class Solution {
    public int lengthOfLongestSubstring(String s) {
        HashMap<Character, Integer> hm = new HashMap<Character, Integer>();
        int max = 0;
        for(int i = 0; i < s.length(); i++) {
            if(!hm.containsKey(s.charAt(i))) {
                hm.put(s.charAt(i), i);
            } else {
                max = Math.max(max, hm.size());
                i = hm.get(s.charAt(i));
                hm.clear();
            }
        }
        return Math.max(max, hm.size());
    }
}

另外我们也可以用两个指针来处理这个题目。两个指针始终维护着一个不包含重复元素的字符串，不断的更新max来得到结果。代码如下：

public class Solution {
    public int lengthOfLongestSubstring(String s) {
        if(s == null || s.length() == 0) return 0;
        int max = 1;
        int start = 0, end = 1;
        String current = s.substring(start, end);
        for(int i = 1; i < s.length(); i++) {
            if(current.indexOf(s.charAt(i)) >= 0 ) {
                max = Math.max(max, end - start);
                start += current.indexOf(s.charAt(i)) + 1;
            }
            end = end + 1;
            current = s.substring(start, end);
        }
        return Math.max(max, end - start);
    }
}