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.
Solution:
Please see the below solution for the answer to the above question.
The algorithm goes like this.
Approach Sliding Window Optimized:
The above solution requires at most 2n steps. In fact, it could be optimized to require only n steps. Instead of using a set to tell if a character exists or not, we could define a mapping of the characters to its index. Then we can skip the characters immediately when we found a repeated character.
The reason is that if s[j] have a duplicate in the range (i, j) with index j. we don’t need to increase i little by little. We can skip all the elements in the range [i,j] and let ii be j+1 directly.
C++ Code Solution:
class Solution {
public:
int lengthOfLongestSubstring(string s) {
if(s.size()==0){return 0;}
if(s.size()==1){return 1;}
int i=0;
int j=0;
int maxl = 0;
map<char,bool> table;
while ( (i<s.size()) && (j<s.size()) ){
if (table[s[j]]==false){
table[s[j]]=true;
maxl = max(maxl,j-i+1);
j++;
}else if (table[s[j]]==true){
maxl = max(maxl,j-i);
table[s[i]]=false;
i++;
}
}
return maxl;
}
};
Python Solution
class Solution:
def lengthOfLongestSubstring(self, s):
start = maxLength = 0
usedChar = {}
for i in range(len(s)):
if s[i] in usedChar and start <= usedChar[s[i]]:
start = usedChar[s[i]] + 1
else:
maxLength = max(maxLength, i - start + 1)
usedChar[s[i]] = i
return maxLength
Follow us on Facebook and Twitter. For questions and queries or suggestions put them in the comment section. Read another article here.
