Longest Substring Without Repeating Characters – LeetCode Problem 3 Explained with Java (Optimal Sliding Window Approach)

Looking for the best way to solve LeetCode Problem 3: Longest Substring Without Repeating Characters? In this post, we’ll explore a Java-based sliding window solution, explain each step, and help you master this classic problem — a favorite in coding interviews at top tech companies.

📘 Problem Overview

You are given a string s. Your task is to return the length of the longest substring that contains no repeated characters.

Example:

• Input: s = "abcabcbb"
• Output: 3
• Explanation: The longest substring without repeating characters is "abc".

💡 Why Use the Sliding Window Approach?

The brute-force method checks every possible substring, leading to O(n²) time complexity — inefficient for large strings.

Instead, we use the sliding window technique along with a HashMap to efficiently find the solution in O(n) time.

✅ Key Concepts of the Sliding Window Technique

1. Two pointers (start and end) define the current window.
2. A HashMap tracks characters and their most recent positions.
3. If a duplicate character is found, move start to the right of the last occurrence.
4. Continuously update the maximum window length without duplicates.

💻 Java Implementation (Optimized)

import java.util.HashMap;

class Solution {
    public int lengthOfLongestSubstring(String s) {
        HashMap<Character, Integer> map = new HashMap<>();
        int maxLen = 0;
        int start = 0;  // Left pointer

        for (int end = 0; end < s.length(); end++) {
            char current = s.charAt(end);
            if (map.containsKey(current)) {
                // Move start only forward
                start = Math.max(map.get(current) + 1, start);
            }
            map.put(current, end);
            maxLen = Math.max(maxLen, end - start + 1);
        }

        return maxLen;
    }
}

🧠 Complexity Analysis

• Time Complexity: O(n) — Each character is visited at most twice (by start and end).
• Space Complexity: O(min(n, m)) — Where m is the number of unique characters (e.g., 26 for lowercase).

🔍 Step-by-Step Explanation

Let’s walk through an example: s = "abcabcbb"

1. Start with an empty HashMap and both pointers at 0.
2. As you iterate:
   • Add characters to the map.
   • If a character repeats, shift the start pointer to the right of its previous occurrence.
   • Continuously track the maximum window length.

✅ For "abcabcbb":

• Longest valid substrings are "abc", "bca", "cab" → max length = 3.

⚠️ Common Pitfalls

• ❌ Not updating start correctly — always move forward.
• ❌ Forgetting to update the character index in the map.
• ❌ Handling edge cases like empty strings or strings with all unique characters.

🛠 Real-World Use Cases

• Input Validation: Ensuring form fields don’t repeat sensitive characters.
• Log Analysis: Detecting patterns or anomalies in real-time data streams.
• Genomic Research: Finding unique gene sequences.

🧪 Test Cases to Try

💬 Final Thoughts

Understanding how to use sliding window and hash maps together is a game-changer for solving string-based problems. Once you master this problem, try tackling:

• ✅ Longest Repeating Character Replacement
• ✅ Minimum Window Substring
• ✅ Substring with Concatenation of All Words

🚀 Start Practicing Now

This problem is frequently asked at companies like Amazon, Google, Microsoft, and Meta. Add it to your practice list and refine your sliding window skills to stand out in interviews.

Happy Coding! 💻🔥