The O(n) Club: Longest Substring Without Repeating Characters: Surviving the Duplicate Juggle

The O(n) Club: Longest Substring Without Repeating Characters — Surviving the Duplicate Juggle

⚡ TL;DR

Asked for the longest substring (contiguous letters!) with no repeats? Brute force checks every substring (good luck if s is longer than your lunch break). Sliding window with a HashSet gives you O(n) time and one less reason to quit dev. Example:

🧠 How Devs Usually Mess This Up

Classic mistakes? First, mixing up substrings and subsequences. (Substrings are glued together, subsequences play hide-and-seek.) Next, the all-too-common O(n³) brute force: three loops, 0 hope. If it takes longer to finish than your coffee, it’s a crime against CPU cycles.

🔍 What’s Actually Going On

Imagine you’re juggling alphabet soup: toss in each letter until you hit a repeat, then drop letters from the left hand until the repeat is gone. That’s your sliding window. With a HashSet tracking unique characters, you can keep the act going—never looking back more than once per letter. If juggling was this organized, most clowns would be engineers.

🛠️ PseudoCode

• Initialize: Start two pointers (left, right) at 0, an empty Set<Character>, and maxLength at 0.
• While right < s.length():
  • If s.charAt(right) is not in the set: add it, update max, step right pointer forward.
  • If duplicate: remove s.charAt(left) and advance left pointer.
• Repeat until right pointer hits the end. Simple as copy-pasting Stack Overflow code.

// Java-esque pseudocode
Set<Character> seen = new HashSet<>();
int left = 0, right = 0, maxLen = 0;
while (right < s.length()) {
  if (!seen.contains(s.charAt(right))) {
    seen.add(s.charAt(right));
    maxLen = Math.max(maxLen, right - left + 1);
    right++;
  } else {
    seen.remove(s.charAt(left));
    left++;
  }
}