3. Longest Substring Without Rep

Description

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

Samples

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.

Solutions

<ol>
<li> O(n)

public class A0003_Longest_Substring_Without_Repeating_Characters {
    public static void main(String[] args) {
        Map<String, Integer> samples = new HashMap<String, Integer>() {
            {
                put("abcabcbb", 3);
                put("bbbb", 1);
                put("pwwkew", 3);
                put("abba", 2);
            }
        };
        for (String string : samples.keySet()) {
            assert solution1(text) == samples.get(text);
        }
    }
    
    /**
     * O(n)
     * 将字符串的字符作为键，其坐标作为值存在map中。使用left和right两个指针代表最大不重复子串的坐标，则最大长度为right-left+1.
     * right不断向后遍历，当发现存在于map中的字符时，更新left的值为上个相同字符的下一坐标，因为这样可以保证子串的字符是互不相同的
     * @return
     */
    public static int solution1(String text) {
        if (text == null || text.length() == 0) return 0;
        HashMap<Character, Integer> map = new HashMap<Character, Integer>();
        int max = 0;
        // include left and right
        for (int right = 0, left= 0; right < text.length(); right++) {
            if (map.containsKey(text.charAt(right))) {
                left = Math.max(left, map.get(text.charAt(right)) + 1);
            }
            map.put(text.charAt(right), right);
            max = Math.max(max, right - left + 1);
        }
        return max;
    }
}