# 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.

## 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```