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.

tags: hash table, string, two pointers

9/21/2015 update

//two pointers algorithm, o(n)
class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        unordered_map<char, int> map;
        int i, j;
        int ans = 0;
        i = j = 0;
        while(j < s.size()){
            if(map.find(s[j]) != map.end()){
                //appeared before
                map.erase(s[i]);
                i++;
            }
            else{
                //not appeared before
                map[s[j]] = 1;
                ans = max(ans, j - i + 1);
                j++;
            }
        }
        return ans;
    }
};

题目不难，很容易找到暴力搜的方法，o(n^2)。我没有用到hash table。只是用两个指针做了简单的优化。也AC了。

一个stirng的一个成员函数find(CharT* s, size_type pos, size_type count)。s指要匹配的子字符串，pos表示在原始字符串中搜索的起始位置，count是指匹配s的前多少个字符，而不是在原始字符串中搜索多少个字符。不要弄错。

如果用hashtable，则可以达到o(n)的复杂度。

hashtable的key为字符，value为一个包含该字符出现位置的数组，这样可以不用find函数，而是通过查哈希表来实现find的操作。

进一步优化，value用一个set来实现，这样每次查value时可以优化到o(logn)。一些代码草稿，未经验证。

//本题中，一个利用hashtable的范例，代替版本一中的string的find函数。
//只是思路，未经编译验证
unordered_map<char, set<int >index> m;
int find(char c, int pos){
	if(m.find(c) == m.end()){
		return -1;
	}
	else{
		return *m[c].lower_bound();
	}
}

版本一：

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        int start = 0;
        int maxLength = 0;
        for(int i = 0; i < s.size(); i++){
            int pos = s.find(s[i], start);
            if(pos != string::npos && pos < i){//repeat in substring
                start = pos + 1;
            }
            else{
                if(i - start + 1 > maxLength){
                    maxLength = i - start + 1;
                }
            }
        }
        return maxLength;
    }
};