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 i*i* 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**.