LeetCode 3，LeetCode

LeetCode 3，LeetCode

Longest Substring Without Repeating CharactersMay 16 '11

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.

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        vector<int> p(256, -1);
        int len = 0;
        int i = 0;
        int max_len = 0;
        for (int j = 0; j < s.length(); j++) {
            if (i > p[s[j]]) {
                len++;
            } else {
                i = p[s[j]] + 1;
                len = j - i + 1;
            }
            p[s[j]] = j;
            max_len = max(max_len, len);
        }
        return max_len;
    }
};

求最长不重复子串的长度：

p[]记录每个字母在字符串s中上次出现的位置，i和j分别是当前子串的首尾，len为当前子串的长度。

从左到右扫描s，如果s[j]在当前字串中没有出现过，len++；否则，新的字串的从s[j]上次出现位置的下一个位置开始，更新当前子串的长度。