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:

// Brute force approach: You're better than this
int maxLen = 0;
for (int i = 0; i < s.length(); i++) {
  for (int j = i + 1; j <= s.length(); j++) {
    String sub = s.substring(i, j);
    if (allUnique(sub)) maxLen = Math.max(maxLen, sub.length());
  }
}
// Slooooow. Try explaining this in an interview without crying.

🧠 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++;
    }
  }