Let me continue my work here.

## Longest substring without Repeating Characters

**Problem Statement**:

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

**Example 1:**

Input:"abcabcbb"Output:3Explanation:The answer is`"abc"`

, which the length is 3.

**Example 2:**

Input:"bbbbb"Output:1Explanation:The answer is`"b"`

, with the length of 1.

**Example 3:**

Input:"pwwkew"Output:3Explanation:The answer is`"wke"`

, with the length of 3. Note that the answer must be asubstring,`"pwke"`

is asubsequenceand not a substring.

**Solution One: Brute Force**

Just a simple and brutal solution. First we iterate all possible sub strings and then we check whether characters in this string are all unique. Since we have to iterate the string from an outer loop and inner loop, the time complexity for these loops are:

n-1 + n – 2 + …. + 1 = (n – 1) * n / 2

which is O(n^2), however, for each sub-string we have extracted, we need to check whether it has identical character, which is O(n). Sum it together, we get the O(n^3).

The space complexity depends on the characters in the string. If all of the characters are unique, and our set will never contain identical characters, then the maximum size of our unordered_set is max number of our characters, let’s say m. However, it’s highly possible that our string is less than m, so the space complexity should be O(min(m,n)).

Time complexity: O(n^3)

Space complexity: O(min(m,n))

This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.

Learn more about bidirectional Unicode characters

class Solution { | |

public: | |

bool isAllUnique(string &s, int start, int end) | |

{ | |

unordered_set<char> hash; | |

for(int i = start; i <= end; i++) | |

{ | |

if(hash.find(s[i]) != hash.end()) | |

return false; | |

hash.insert(s[i]); | |

} | |

return true; | |

} | |

int lengthOfLongestSubstring(string s) { | |

int len = s.size(); | |

int maxLen = s.empty()? 0 : 1; | |

for(int i = 0; i < len; i++) | |

{ | |

for(int j = i + 1; j< len; j++) | |

{ | |

if(isAllUnique(s, i, j)) | |

maxLen = max(j – i + 1, maxLen); | |

} | |

} | |

return maxLen; | |

} | |

}; |

**Solution Two: Sliding
**

The brute force algorithm is extremely slow. How can we do better?

Let’s observe what is going on when we run the loop… When the loop begins:

j = 1, check string[0:1], whether the sub-string is unique;

j = 2, check string[0:2], whether the sub-string is unique;

j = 3, check string[0:3], whether the sub-string is unique;

…

Can you see it, we have done a lot of repetitive job. If we already know that string[0:3] contains an identical character, we do not need to check string[0:3] anymore in string[0:4], we just need to check whether string[3] is in the string[0:3]… if it is, then string[3] is not an unique character, which means that string[0:4] must contain identical characters, so all the following string[0:n] must contain identical characters, we do not need to increase j any more, we just directly increase i; if it is not, then j moves forward, and put string[3] in the set.

Another potential improvement is, when we find that a sub string contains an identical character, we do not need to increase i one by one. We can just make i jump directly to the next position of first identical character, then the loop continues.

Since we only iterate j in the loop and make i jump from point to point, so the whole running time should be O(n). The space complexity should be the same as the solution one (we still need to maintain the hash table).

Time complexity: O(n)

Space complexity: O(min(m,n))

This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.

Learn more about bidirectional Unicode characters

class Solution { | |

public: | |

int lengthOfLongestSubstring(string s) { | |

unordered_map<char, int> set; | |

int n = s.size(); | |

int i=0, j=0, maxLength = 0; | |

while(i<n&&j<n) | |

{ | |

if(set.find(s[j])!=set.end()) | |

{ | |

i = max(i,set[s[j]]); | |

set.erase(s[j]); | |

} | |

else | |

{ | |

set[s[j]] = j + 1; | |

maxLength = max(maxLength, j-i+1); | |

j++; | |

} | |

} | |

return maxLength; | |

} | |

}; |

**Solution Three: Character Dictionary
**

This is a tricky solution. Instead of tracking each character in the string, we first build a dictionary array which contains all the possible characters. When we iterate our string, we put the index of each character to the dictionary and track our first index of a unique sub string using a variable named as start, then we increase our iteration and find the same character as the first one of this unique sub string , we can calculate the length of this unique sub string:

i – start; // start is initially set as -1;

We only update our start variable when we encounter an identical character, and we set start variable be the index of that first identical character. After that, we calculate the length of this sub string and compare it with the max length.

The time complexity of this solution is O(n), since we iterate the string once. While the space complexity is equal to character types. We have to use the same number of space as numbers of character types. It might be more useful for English Ascii characters. Since it is very powerful when we want to check a very long string which contains only Ascii characters.

Time complexity: O(n)

Space complexity: O(m) m is the number of character types.

This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.

Learn more about bidirectional Unicode characters

class Solution { | |

public: | |

int lengthOfLongestSubstring(string s) { | |

vector<int> dict(256,-1); | |

int maxLength = 0, start = –1; | |

for(int i =0; i<s.size(); i++) | |

{ | |

if(dict[s[i]] > start) | |

start = dict[s[i]]; | |

dict[s[i]] = i; | |

maxLength = max(maxLength, i – start); | |

} | |

return maxLength; | |

} | |

}; |

That’s all for this article…