Longest Substring Without Repeating Characters problem and solution in Java and Python

This is one of the most common sliding window problems asked in FAANG interviews. Let’s go step-by-step — from simple explanation to optimized Java and Python code.

---

🧩 Problem: Longest Substring Without Repeating Characters

You are given a string s. Find the length of the longest substring that contains no repeating characters.

---

💡 Example 1

Input: s = "abcabcbb"
Output: 3
Explanation: The answer is "abc", with length 3.

💡 Example 2

Input: s = "bbbbb"
Output: 1
Explanation: "b" is the longest substring without repeats.

💡 Example 3

Input: s = "pwwkew"
Output: 3
Explanation: "wke" is the longest substring.

---

🧒 Explained to a Kid

Imagine you’re reading letters one by one and writing them on a board. If a letter repeats — you erase everything up to the previous same letter and continue writing from there.

At any point, you want to know the longest board of unique letters you’ve had so far.

---

🧠 Intuition: Sliding Window

You can solve this using a sliding window — think of a window that expands and shrinks dynamically to keep only unique characters.

• Use two pointers: left and right

• Use a Set or Map to track characters in the current window

• Expand the right pointer and add characters

• If a character repeats:

  • Shrink from the left until it’s unique again

• Keep track of the maximum window length

---

🐢 Brute Force (for understanding)

Check all substrings and verify if each has all unique characters.

• Time: O(n³) (generate + check uniqueness)
• Not efficient ❌

---

⚡ Optimized Sliding Window Approach (O(n))

Key Idea:

Maintain a window of non-repeating characters.

• Expand right pointer by adding new characters.
• If a character repeats, move left pointer to remove duplicates.
• Keep updating the max length.

---

💻 Java Implementation

import java.util.*;

public class LongestSubstring {
    public static int lengthOfLongestSubstring(String s) {
        Set<Character> set = new HashSet<>();
        int left = 0, maxLen = 0;

        for (int right = 0; right < s.length(); right++) {
            while (set.contains(s.charAt(right))) {
                set.remove(s.charAt(left));
                left++;
            }
            set.add(s.charAt(right));
            maxLen = Math.max(maxLen, right - left + 1);
        }
        return maxLen;
    }

    public static void main(String[] args) {
        System.out.println(lengthOfLongestSubstring("abcabcbb")); // Output: 3
        System.out.println(lengthOfLongestSubstring("pwwkew"));   // Output: 3
    }
}

---

💻 Python Implementation

def lengthOfLongestSubstring(s):
    seen = set()
    left = 0
    max_len = 0

    for right in range(len(s)):
        while s[right] in seen:
            seen.remove(s[left])
            left += 1
        seen.add(s[right])
        max_len = max(max_len, right - left + 1)
    
    return max_len

print(lengthOfLongestSubstring("abcabcbb"))  # Output: 3
print(lengthOfLongestSubstring("pwwkew"))    # Output: 3

---

🧮 Optimized Using HashMap (for fast jumps)

Instead of removing one by one, we can jump left pointer directly to skip duplicates faster.

---

💻 Java (HashMap Jump Optimization)

import java.util.*;

public class LongestSubstringOptimized {
    public static int lengthOfLongestSubstring(String s) {
        Map<Character, Integer> map = new HashMap<>();
        int left = 0, maxLen = 0;

        for (int right = 0; right < s.length(); right++) {
            char c = s.charAt(right);
            if (map.containsKey(c)) {
                // Move left pointer to the right of previous duplicate
                left = Math.max(left, map.get(c) + 1);
            }
            map.put(c, right);
            maxLen = Math.max(maxLen, right - left + 1);
        }
        return maxLen;
    }

    public static void main(String[] args) {
        System.out.println(lengthOfLongestSubstring("abcabcbb")); // Output: 3
        System.out.println(lengthOfLongestSubstring("bbbbb"));    // Output: 1
        System.out.println(lengthOfLongestSubstring("pwwkew"));   // Output: 3
    }
}

---

💻 Python (HashMap Jump Optimization)

def lengthOfLongestSubstring(s):
    char_index = {}
    left = 0
    max_len = 0

    for right, c in enumerate(s):
        if c in char_index and char_index[c] >= left:
            left = char_index[c] + 1
        char_index[c] = right
        max_len = max(max_len, right - left + 1)

    return max_len

print(lengthOfLongestSubstring("abcabcbb"))  # Output: 3
print(lengthOfLongestSubstring("bbbbb"))     # Output: 1
print(lengthOfLongestSubstring("pwwkew"))    # Output: 3

---

⚙️ Time & Space Complexity

Approach	Time	Space	Notes
Brute Force	O(n³)	O(1)	Too slow
Sliding Window (Set)	O(n)	O(k)	k = charset size (≤128)
HashMap Jump	O(n)	O(k)	Best, fast skipping duplicates

---

💭 Example Trace

Let’s take "pwwkew":

Step	Left	Right	Window	Action	Max
1	0	0	"p"	Add	1
2	0	1	"pw"	Add	2
3	0	2	"pww"	Duplicate ‘w’, move left	2
4	2	3	"wk"	Add	2
5	2	4	"wke"	Add	3
6	2	5	"wkew"	Duplicate ‘w’, move left	3

✅ Answer = 3

---

🌍 Real-Life Analogy

You’re walking down a street reading signboards. You can only read a unique sequence of signs before you see a repeated one. Whenever you see a repeat, you “forget” up to the last occurrence and start fresh. The longest sequence you manage to read is your answer.

---