Longest Substring Without Repeating Characters

Given a string, find the length of the longest substring without repeating characters. For example, the longest substring without repeating letters for "abcabcbb" is "abc", which the length is 3.

For "bbbbb" the longest substring is "b", with the length of 1. O(n) time

Key Points: O(n) time

1. Maintain two indexes: left and right.
2. Let the right index run to the end. If it meet the barrier, then use left index to break the barrier.

Key Points: O(n) time

pseudocode :

while(right < A.size){

     if(right can move){
         move right;
         change status;
     }
     else{
         move left;
         change status;
     }

     record status;
 }

C++ Solution:

class Solution {
  public:
    int lengthOfLongestSubstring(string s) {
        // use set to check the letters
        unordered_set<char> record;
        int result = 0;
        int left = 0, right = 0;

        while(right < s.size()){
            // move right if can
            if(record.find(s[right]) == record.end()){
                record.insert(s[right++]);
            }
            // if right can't move, record current lenght;
            // move left until right can move
            else{
                record.erase(s[left++]);
            }
            // record current length
            result = max(right-left, result);
        }
        return result;
    }
};