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.

链接: http://leetcode.com/problems/longest-substring-without-repeating-characters/

题解:

Sliding Window，每次在HashMap里放入当前字符的index i。要注意start何时更新。比如abba这种情况。

需要修改，Space Complexity可被降低到O(1)。想了想，O(1)的做法是开一个int[256]的array，其实在扩展的ASC II码范围内，我们的HashMap也不会超过256个keyset，因为每次我们都put，覆盖掉了，应该也能算O(1)吧...

Time Complexity - O(n)，Space Complexity - O(n)

public class Solution {
    public int lengthOfLongestSubstring(String s) {
        if(s == null || s.length() < 2)
            return s.length();
        int max = 0, start = 0;
        HashMap<Character, Integer> map = new HashMap<Character, Integer>();
        
        for(int i = 0; i < s.length(); i++){
            if(map.containsKey(s.charAt(i)))
                if(map.get(s.charAt(i)) >= start)
                    start = map.get(s.charAt(i)) + 1;
            map.put(s.charAt(i), i);
            max = Math.max(max, i - start + 1);
        }
        
        return max;
    }
}

二刷:

Java:

public class Solution {
    public int lengthOfLongestSubstring(String s) {
        if (s == null || s.length() == 0) {
            return 0;
        }
        Map<Character, Integer> map = new HashMap<>();
        int max = 0;        
        for (int i = 0, index = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if (map.containsKey(c) && map.get(c) >= index) {
                index = map.get(c) + 1;
            }
            map.put(c, i);
            max = Math.max(i - index + 1, max);
        }
        
        return max;
    }
}

Python:

class Solution(object):
    def lengthOfLongestSubstring(self, s):
        """
        :type s: str
        :rtype: int
        """
        maxLen = 0
        index = 0
        dict = {}
        for i, char in enumerate(s):
            if char in dict and dict[char] >= index:
                index = dict[char] + 1
            dict[char] = i
            maxLen = max(maxLen, i - index + 1)
        return  maxLen

三刷:

题目没有说明alphabet只是 single byte chars，所以我觉得还是用HashMap比较好一些。但其实试了几次以后发现test case只包含扩展ASCII码的元素，所以我们可以投机取巧用一个int[256]的数组来取得更快的速度。

为什么条件是map.get(c) >= lo呢？就是对于"abba"这种情况，当访问第二个"a"的时候，map.get(a) = 0，但lo已经是2了，所以不用更新lo.

Java:

HashMap:

Time Complexity - O(n), Space Complexity - O(n)。

public class Solution {
    public int lengthOfLongestSubstring(String s) {
        if (s == null || s.length() == 0) {
            return 0;
        }
        int max = 1, lo = 0;
        Map<Character, Integer> map = new HashMap<>();
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if (map.containsKey(c) && map.get(c) >= lo) {
                lo = map.get(c) + 1;
            }
            max = Math.max(max, i - lo + 1);
            map.put(c, i);
        }
        return max;
    }
}

使用bitmap:

这里假定alphabet为 single-byte char，Space Complexity可以认为是O(1)。

写的时候使用了一个小技巧: 因为int[]数组初始值为0，我们后面比较的时候不方便，所以在写的时候我们可以把 0 - based转换为 1 - based，也就是说我们的使用的index从1开始。这样我们可以设置lo = 1，每次更新bitmap里值的时候可以设置为i + 1。计算maxLen的时候要用max (maxLen, i - lo + 2)。这样做的好处是，我们在判断是否更新lo的时候只需要一个比较 - bitmap[c] >= lo，从而跳过了bitmap[c] = 0的case。不知道这样作是否值得...

另外，当if clause里只有一条语句的时候，我们也可以简写，比如 if (bitmap[c] >= lo) lo = bitmap[c] + 1。还有缩进的话，假如按照google java standard，是缩进两个字符，不是四个。 coding convention这些东西还需要好好学习和练习，争取熟练以后总结出一套自己顺手，并且可读性较好的规则。

Time Complexity - O(n), Space Complexity - O(1)。

public class Solution {
    public int lengthOfLongestSubstring(String s) {
        if (s == null || s.length() == 0) {
            return 0;
        }
        int maxLen = 1, lo = 1;
        int[] bitmap = new int[256];
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if (bitmap[c] >= lo) {
                lo = bitmap[c] + 1;
            }
            maxLen = Math.max(maxLen, i - lo + 2);
            bitmap[c] = i + 1;
        }
        return maxLen;
    }
}