Longest Substring Without Repeating Characters

🧩 What’s the Problem?

Imagine you’re walking through a street full of shops, each selling unique items (characters from a string). You’re on a mission: find the longest stretch of shops where no shop repeats an item you’ve already bought.

So, your task is:

• You’re given a string s, and you need to find the longest substring where all the characters are unique.
• Think of it like walking along a street and never revisiting any shop you’ve already been to.

🎯 Example

Let’s take a look at a simple string:

s = "abcabcbb"

The longest substring without repeating characters is: abc.

Why? Because the first time you encounter a, b, and c, they’re all unique. But the second time you hit a, that breaks the rule.

🔑 How Does the Code Work?

Let’s break this down into simple steps.

You’re going to use two pointers:

• The first pointer, left, represents the start of your current window (your current stretch of shops).
• The second pointer, right, represents where you are currently standing (the shop you’re at now).

The key idea:

1. As you move forward, you keep track of the shops (characters) you’ve visited.
2. If you encounter a shop (character) you’ve already visited, you move the left pointer forward until you’ve removed the duplicate.
3. Your goal is to always keep a window with unique characters.

Let’s simplify the solution with an easy-to-remember pattern:

1. Start with the right pointer moving forward through the string.
2. If you find a duplicate, move the left pointer forward until there are no duplicates.
3. Keep track of the longest window you’ve found.

📖 The Code

Here’s the code to do this:

class Solution

{

public int lengthOfLongestSubstring(String s)

{

HashSet<Character> set = new HashSet<>(); // Your collection of visited shops

int MaxLength = 0; // Store the length of the longest unique window

int left = 0; // Left pointer (start of the window)

for (int right = 0; right < s.length(); right++) // Right pointer (exploring the shops)

{

while (set.contains(s.charAt(right))) // If the current shop is a duplicate

{

set.remove(s.charAt(left)); // Remove the shop from the window

left++; // Move the left pointer to skip over the duplicate

}

set.add(s.charAt(right)); // Add the current shop to the window

MaxLength = Math.max(MaxLength, right - left + 1); // Update the max length

}

return MaxLength; // Return the longest unique window

}

}

Let's Walk Through It!

We’ll walk step-by-step through the string:

s = "abcabcbb"

Here’s what we start with:

• left = 0 ➡️ the start of your window (your current stretch of shops).
• right = 0 ➡️ your current location on the street.
• MaxLength = 0 ➡️ keeps track of the longest walk with no repeats.
• set = {} ➡️ your shopping bag 🛍️ filled with the unique items you’ve picked up.

🧭 Step-by-step Breakdown

Step 1: right = 0 → 'a'

• Have you picked up 'a' before? Nope! ✅
• Add 'a' to your bag: set = {'a'}
• Window size = right - left + 1 = 0 - 0 + 1 = 1
• Update MaxLength = 1
• 🎉 Window is 'a'

Step 2: right = 1 → 'b'

• Is 'b' in your bag? Nope! ✅
• Add 'b': set = {'a', 'b'}
• Window size = 1 - 0 + 1 = 2
• Update MaxLength = 2
• 🎉 Window is 'ab'

Step 3: right = 2 → 'c'

• Seen 'c'? Nope! ✅
• Add 'c': set = {'a', 'b', 'c'}
• Window size = 2 - 0 + 1 = 3
• Update MaxLength = 3
• 🎉 Window is 'abc'

Step 4: right = 3 → 'a'

• Uh-oh! 'a' is already in your bag! ❌
• Time to move the left pointer and drop items until 'a' is gone.

1. Remove s[left] = 'a': set = {'b', 'c'}, left = 1 ✅
2. Now 'a' is safe to add!

• Add 'a': set = {'a', 'b', 'c'}
• Window size = 3 - 1 + 1 = 3
• MaxLength remains 3
• 🎉 Window is 'bca'

Step 5: right = 4 → 'b'

• Oh no, ‘b’ is a duplicate again! ❌

1. Remove s[left] = 'b': set = {'a', 'c'}, left = 2 ✅
2. Now add 'b': set = {'a', 'b', 'c'}

• Window size = 4 - 2 + 1 = 3
• MaxLength still 3
• 🎉 Window is 'cab'

Step 6: right = 5 → 'c'

• Duplicate again! 'c' is in your bag! ❌

1. Remove s[left] = 'c': set = {'a', 'b'}, left = 3 ✅
2. Add 'c': set = {'a', 'b', 'c'}

• Window size = 5 - 3 + 1 = 3
• MaxLength still 3
• 🎉 Window is 'abc' again!

Step 7: right = 6 → 'b'

• Duplicate alert! 'b' again ❌

1. Remove s[left] = 'a': set = {'b', 'c'}, left = 4
2. Remove s[left] = 'b': set = {'c'}, left = 5
3. Now add 'b': set = {'b', 'c'}

• Window size = 6 - 5 + 1 = 2
• MaxLength remains 3
• 🎉 Window is 'cb'

Step 8: right = 7 → 'b'

• 'b' again?! We just saw you! ❌

1. Remove s[left] = 'c': set = {'b'}, left = 6
2. Remove s[left] = 'b': set = {}, left = 7
3. Now add 'b': set = {'b'}

• Window size = 7 - 7 + 1 = 1
• MaxLength still 3
• 🎉 Window is 'b'

🏁 Final Result

• After walking through the entire string:
• The longest window without repeating characters was 'abc'
• Final MaxLength = 3

💡 Why This Works

Time Efficiency:

The algorithm moves each pointer only once through the string. This gives you a time complexity of O(n), where n is the length of the string. We don’t waste time checking every possible substring.

Space Efficiency:

We’re only storing the characters that are part of the current window (substring), so we’re using O(min(n, m)) space, where n is the string length and m is the number of unique characters (which is small, usually 256 for ASCII characters).

🔄 Takeaways

1. Two pointers — The left pointer adjusts to avoid duplicates while the right pointer expands the window.
2. Set — This helps you quickly check if a character has already been encountered in the current window.
3. Max length — Update the maximum length of the window whenever the current window is larger than the previous longest window.

Practice It!

You can try this solution on other strings:

s = "pwwkew"

The longest unique substring is wke, length 3.

🎯 The Final Tip

• Think of it like a fun game of exploring a street of shops:
• Keep walking (with your right pointer).
• If you see something you’ve already seen (a duplicate), move back (move your left pointer) until you find a new path (unique substring).
• Keep track of the longest stretch you’ve found!