Oct 01, 2017

# Longest Substring Without Repeating Characters

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.

int lengthOfLongestSubstring(string s) {
int i = 0,j = 0;
int ret = 0;
map<char,bool> cbmap;
while( j < s.size() ){
while(j < s.size() && cbmap[s[j]] == false)
cbmap[ s[j++] ] = true;
ret = max(j-i,ret);
while(i < j && cbmap[s[j]] != false)
cbmap[ s[i++] ] = false;
cbmap[ s[j++] ] = true;
}
return ret;
}


• 用两个下标来标识Substring的位置，s[i,j)就是我们当前的Substring.
• 用j去遍历整个串，如果当前子串中没有s[j]j就继续往下遍历，如果有，这时就可以计算一下当前子串的长度和之前的最长子串长度进行对比。
• j停止遍历后，我们就让i向前移动，直到，当前子串不包含s[j],这样我们就可以把s[j]加入当前子串，并继续进行遍历。

int lengthOfLongestSubstring(string s) {
int ret = 0;
map<char,bool> cbmap;
for(int i = 0,j = 0; j < s.size();j++ ){
while(j < s.size() && cbmap[s[j]] == false)
cbmap[ s[j++] ] = true;
ret = max(j-i,ret);
while(i < j && s[i++] != s[j])
cbmap[ s[i - 1] ] = false;
}
return ret;
}


int lengthOfLongestSubstring(string s) {
// for ASCII char sequence, use this as a hashmap
vector<int> charIndex(256, -1);
int longest = 0, m = 0;

for (int i = 0; i < s.length(); i++) {
m = max(charIndex[s[i]] + 1, m);    // automatically takes care of -1 case
charIndex[s[i]] = i;
longest = max(longest, i - m + 1);
}

return longest;
}



LeetCodeLeetCode

Maximum Product Subarray

Add Two Numbers

comments powered by Disqus