【LeetCode-Algorithms】3. Longest

题目:

Given a string, find the length of the longest substring without repeating characters.
Examples:
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.

题目大意：

给定一个字符串，找到最长子字符串的长度而不重复字符。
例子：
给定"abcabcbb"，答案是"abc"，长度为3
给定"bbbbb"，答案是"b"，长度为1
给定"pwwkew"，答案是"wke"，长度为3.请注意，答案必须是子字符串，"pwke"是子序列而不是子字符串

具体实现

//1：基本的实现方案
class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        int pos = 0;
        int max_len = 0;
        string strstr = "";
        string max_str = "";

        for (int i = 0; i < s.size(); ++i) {
            pos = strstr.find(s[i]);
            if (pos != -1) {
                if (strstr.size() > max_len) {
                    max_len = strstr.size();
                    max_str = strstr;
                }
                strstr = strstr.substr(pos+1, strstr.size());
            }
            strstr += s[i];
        }

        if (strstr.size() > max_len) {
            max_len = strstr.size();
            max_str = strstr;
        }
        return max_len;
    }
};

// 2：牛逼的解决方案
int lengthOfLongestSubstring(string s) {
        vector<int> dict(256, -1);
        int maxLen = 0, start = -1;
        for (int i = 0; i != s.length(); i++) {
            if (dict[s[i]] > start)
                start = dict[s[i]];
            dict[s[i]] = i;
            maxLen = max(maxLen, i - start);
        }
        return maxLen;
}