SimuVedaAlgorithms Lab Open in the lab

Hashing / Intermediate

Longest Substring Without Repeats Visualizer

Grow the window to the right one letter at a time. A hash map remembers where each letter was last seen; on a repeat inside the window, jump the left edge just past that earlier copy.

Start the Longest Substring Without Repeats simulation → Step forward and back, change the input, follow the code line by line in Java, Python, C++, C or JavaScript. Free, no sign-up.

Time and space complexity

Best timeO(n)
Average timeO(n)
Worst timeO(n)
Extra spaceO(k)

Worked example, step by step

The same steps the simulator shows, on a small input.

  1. Window is empty: left = 0, best = 0.
  2. Add "a" at index 0 to the window.
  3. Window "a" has length 1. New best.
  4. Add "b" at index 1 to the window.
  5. Window "ab" has length 2. New best.
  6. Add "c" at index 2 to the window.
  7. Window "abc" has length 3. New best.
  8. Add "a" at index 3 to the window.
  9. "a" was already seen at index 0, inside the window.
  10. Move left past it to 1.
  11. Window "bca" has length 3. Best stays 3.
  12. Add "b" at index 4 to the window.
  13. "b" was already seen at index 1, inside the window.
  14. Move left past it to 2.
  15. Window "cab" has length 3. Best stays 3.
  16. Add "c" at index 5 to the window.
  17. "c" was already seen at index 2, inside the window.
  18. Move left past it to 3.
  19. Window "abc" has length 3. Best stays 3.
  20. Add "b" at index 6 to the window.
  21. … 4 more steps …
  22. "b" was already seen at index 6, inside the window.
  23. Move left past it to 7.
  24. Window "b" has length 1. Best stays 3.
  25. Done. The longest substring without repeats is "abc", length 3.

Try it with your own input →

Longest substring without repeats in Java, Python, C++, C and JavaScript

int lengthOfLongestSubstring(String s) {
  Map<Character, Integer> last = new HashMap<>();
  int best = 0, left = 0;
  for (int right = 0; right < s.length(); right++) {
    char c = s.charAt(right);
    if (last.containsKey(c) && last.get(c) >= left)
      left = last.get(c) + 1;
    last.put(c, right);
    best = Math.max(best, right - left + 1);
  }
  return best;
}
def length_of_longest_substring(s):
    last = {}
    best = left = 0
    for right in range(len(s)):
        c = s[right]
        if c in last and last[c] >= left:
            left = last[c] + 1
        last[c] = right
        best = max(best, right - left + 1)
    return best
int lengthOfLongestSubstring(const string& s) {
  unordered_map<char, int> last;
  int best = 0, left = 0;
  for (int right = 0; right < (int)s.size(); right++) {
    char c = s[right];
    if (last.count(c) && last[c] >= left)
      left = last[c] + 1;
    last[c] = right;
    best = max(best, right - left + 1);
  }
  return best;
}
#include <string.h>

int lengthOfLongestSubstring(const char* s) {
  int last[256];
  for (int c = 0; c < 256; c++) last[c] = -1;
  int best = 0, left = 0, n = strlen(s);
  for (int right = 0; right < n; right++) {
    unsigned char c = s[right];
    if (last[c] >= left)
      left = last[c] + 1;
    last[c] = right;
    if (right - left + 1 > best) best = right - left + 1;
  }
  return best;
}
function lengthOfLongestSubstring(s) {
  const last = new Map();
  let best = 0, left = 0;
  for (let right = 0; right < s.length; right++) {
    const c = s[right];
    if (last.has(c) && last.get(c) >= left)
      left = last.get(c) + 1;
    last.set(c, right);
    best = Math.max(best, right - left + 1);
  }
  return best;
}

In an interview

LeetCode 3, Longest Substring Without Repeating Characters. Same window: 340 (at most k distinct), 424 Longest Repeating Character Replacement.

Jumping left with the map is O(n). Moving left one step at a time with a set is also O(n), since each letter enters and leaves once. Mention both.

More hashing