Longest Substring without Repeating Characters

Concepts

https://leetcode.com/articles/longest-substring-without-repeating-characters/#approach-2-sliding-window-accepted

• Hash map / Hash set

• Sliding Window

• initialize hash map, start, end, and answer

• loop through such that start and end are both not passing the string's length

  1. if the hash map does not contain the last checked character:
     1. mark it as checked
     2. increment end
     3. if end - start is greater than the current answer
        1. make end - start the new current answer
  2. else
     1. mark the hash map containing the current character at start as true
     2. increment start

Things to Note:

• The algorithm will keep iterating the start until we are at the last point we saw the end character. This is important to note because we are unsetting every character before the character matching the end character. This is the back part of the sliding window. It will continue to slide up until the new substring is set. This new substring will only be set as the new one if end - start is greater than the previously saved answer.

int longestSubString(string str)
{
  bool charMap[128];
  int start = 0, end = 0, ans = 0;
  while( start < str.length() && end < str.length()) {
    if(charMap[str[end]] == false) {
     charMap[str[end]] = true;
     end++;
     ans = max(ans, end - start);
    }
    else {
      charMap[s[start]] = false;
      start++;
    }
  }
  return ans;
}

Complexity

Space: 128 bools, 3 ints

Time: O(2n) = O(n)