Longest Substring Without Repeating Characters

LeetCode #3

Description:

Given a string, find the length of the longest substring without repeating characters.

Example:

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.

Idea:

有大小写或者别的字符#$。建立一个256个的数组，存每个字符前一次出现的位置。char可以当做index来用，因为char可以用作int值。

每次update max_len的值,如果遇到重复字符，如果在现start之前不管，在start之后需要update start的位置。

Code:

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        // record the location of recently appeared character
        vector<int> location(256, -1);

        int max_len=0;
        int start=0;

        for(int j=0; j<s.size(); ++j){

            if(location[s[j]]>=start){
                start=location[s[j]]+1;
            }

            location[s[j]]=j;
            max_len = max(j-start+1, max_len);
        }

        return max_len;
    }
};