Longest Substring Without Repeating Characters

Given a string, find the length of the longest substring without repeating characters. http://www.lintcode.com/en/problem/longest-substring-without-repeating-characters/

Discussion

需要限定character的范围，小写字母？大写字母？数字？ASCII？

最初的方案是用个hash保存当前的substring，因为要看是否重复嘛，hash查找方便。一旦遇到重复字符，就update hash和最大长度。update hash是把重复字符第一次出现之前的都erase掉。这种情况下是不需要考虑character的范围的，但是提交就是通不过，wrong answer，但是我本地debug出来明明是好的。方案如见Solution 1。

方案2是假定ASCII，定义个256的数组，来表示这个字符有没有出现过。用两个指针，j指向当前字符，如果当前字符有出现过，讲i指向该字符第一次出现位置的下一个位置，然后更新maxlen。这个不难理解，可是实现的时候我觉得太有技巧了，臣妾做不到。。。于是照着这个思想写了Solution 3.

Solution 1

class Solution {
public:
    /**
     * @param s: a string
     * @return: an integer 
     */
    int lengthOfLongestSubstring(string s) {
        // write your code here
        int maxlen = 0;
        unordered_map<char, bool> map;
        for(int i=0; i<s.length(); i++) {
            char c = s[i];
            unordered_map<char, bool>::iterator it=map.find(c);
            if(it != map.end()) {//找到了就更新maxlen，erase map
                if(map.size() > maxlen) {
                    maxlen = map.size();
                }
                map.erase(map.begin(), next(it));//it+1报错，因为iterator类型不支持+operator。所以以后涉及iterator
                //的操作就用next，prve， advance（return void)好了.
            } 
            map[c] = true;
        }
        if(map.size() > maxlen)//最后一个map也要比较
            maxlen = map.size();
        return maxlen;
    }
};

差不多的思路，不用hash的解法：

class Solution {
public:
    /**
     * @param s: a string
     * @return: an integer 
     */
    int lengthOfLongestSubstring(string s) {
        int result = 0;
        if(s.empty()) return result;
        string sub = s.substr(0, 1);
        result = 1;
        int start = 0;
        for(int i=1; i<s.length(); i++) {
            auto pos = sub.find(s[i]);
            if(pos == string::npos) {//non-repeating character
                sub.push_back(s[i]);
            } else {
                sub.erase(sub.begin(), sub.begin() + pos + 1);
                sub.push_back(s[i]);
            }
            if(sub.length() > result) {
                result = sub.length();
            }
        }
        return result;
    }
};

Solution 2

class Solution {
public:
    /**
     * @param s: a string
     * @return: an integer 
     */
    int lengthOfLongestSubstring(string s) {
        // write your code here
        bool exist[256] = {false};
        int i=0; 
        int maxlen = 0;
        for(int j=0; j<s.length(); j++) {
            while(exist[s[j]]) {//如果有重复字符出现，i最终指向重复字符第一次出现的位置的下一个字符，太难想了
                exist[s[i]] = false;
                i++;
            }
            exist[s[j]] = true;
            maxlen = max(j-i+1, maxlen);
        }
        return maxlen;
    }
};

Solution 3

class Solution {
public:
    /**
     * @param s: a string
     * @return: an integer 
     */
    int lengthOfLongestSubstring(string s) {
        // write your code here
        int exist[256];//存的是字符出现的位置
        for(int i=0; i<256; i++) {
            exist[i] = -1;
        }
        int i=0; 
        int maxlen = 0;
        for(int j=0; j<s.length(); j++) {
            if(exist[s[j]] >=i) {//找到出现过的字符的下一个字符
                i = exist[s[j]]+1;
            }
            exist[s[j]] = j;
            maxlen = max(j-i+1, maxlen);
        }
        return maxlen;
    }
};