Longest Substring Without Repeating Characters: Visual Guide & 5 Code Solutions

Imagine you're building a plagiarism checker that needs to scan a document and flag the longest continuous chunk of text that doesn't repeat any character. Or perhaps you're working on a data deduplication tool for streaming network packets, trying to identify the longest unique sequence in real time. This is exactly the problem we'll solve today: finding the longest substring without repeating characters.

Given a string like "abcabcbb", the answer is 3 — corresponding to "abc". It's a classic coding interview question that appears on LeetCode (Problem #3) and in countless technical screens at companies like Google, Amazon, and Microsoft. The optimal solution relies on the sliding window algorithm, a pattern you'll use again and again.

In this guide, I'll walk you through everything: the brute force approach (so you understand why we need optimization), the optimal sliding window solution with a visual animation, and complete implementations in Python, Java, JavaScript, C++, and Go. I'll also cover edge cases, real-world applications, and common variations.

---

Understanding the Problem: Substring vs. Subsequence

Problem Definition and Examples

Formally: Given a string s, find the length of the longest substring without repeating characters.

Let's look at a few examples to make this concrete:

Why This Problem Matters in Coding Interviews

I've sat on both sides of the interview table, and I can tell you this problem shows up with remarkable frequency. It's consistently ranked among the top 10 most-asked problems on LeetCode [需核实], and for good reason.

This problem tests several fundamental skills simultaneously:

• Data structures: You need a hash set or hash map to track character positions.
• String manipulation: Understanding indices and window boundaries.
• Algorithmic thinking: Recognizing when a brute force approach is too slow and knowing how to optimize.

More importantly, it's a gateway to the sliding window pattern, which appears in problems like Minimum Window Substring, Longest Repeating Character Replacement, and Find All Anagrams in a String. Once you master the sliding window here, you'll recognize the pattern in dozens of other problems.

Interviewers typically ask for a brute-force solution first, then push you toward optimization. This progression reveals how you think under pressure — whether you can identify inefficiencies and iterate toward a better solution.

---

Brute Force Approach: The Naive Solution

Algorithm Explanation

The most straightforward approach: generate every possible substring and check if it contains any repeating characters.

Here's the logic:

1. Use two nested loops to generate all substrings — the outer loop sets the start index i, the inner loop sets the end index j.
2. For each substring s[i:j+1], check if all characters are unique using a set.
3. Track the maximum length found.

Here's what that looks like in Python:

def length_of_longest_substring_brute_force(s: str) -> int:
    n = len(s)
    max_length = 0
    
    for i in range(n):
        for j in range(i, n):
            # Check if substring s[i:j+1] has all unique characters
            char_set = set()
            valid = True
            for k in range(i, j + 1):
                if s[k] in char_set:
                    valid = False
                    break
                char_set.add(s[k])
            
            if valid:
                max_length = max(max_length, j - i + 1)
    
    return max_length

This works, but it's painfully slow. Let's break down why.

Time and Space Complexity Analysis

Time complexity: O(n³) — Three nested loops. The outer two loops generate all substrings (O(n²) substrings), and for each one, we potentially scan all its characters (O(n) in the worst case).

Space complexity: O(min(n, m)) — The set stores at most the number of unique characters in the current substring, where m is the size of the character set (e.g., 26 for lowercase letters, 128 for ASCII).

---

Optimal Solution: The Sliding Window Algorithm with Hash Map

Core Intuition and Algorithm Steps

The key insight: when we find a duplicate character, we don't need to restart from scratch. We can simply slide the left boundary of our window past the previous occurrence of that duplicate.

Here's the algorithm:

1. Initialize two pointers: left = 0 and right = 0.
2. Use a hash map to store each character's most recent index.
3. Expand the window by moving right forward.
4. If the current character is already in the map and its stored index is within the current window, move left to previous_index + 1.
5. Update the character's index in the map.
6. Track the maximum window length.

Let me walk through s = "abcabcbb" step by step:

Visual Animation: How the Window Moves

Imagine a highlighted window sliding over the string. The window starts empty at position 0. As the right pointer moves forward, the window expands. When a duplicate is found, the left edge jumps forward, and the window shrinks.

Here's a conceptual visualization for "abcabcbb":

Step 1: [a] b c a b c b b     → window: "a", max: 1
Step 2: [a b] c a b c b b     → window: "ab", max: 2
Step 3: [a b c] a b c b b     → window: "abc", max: 3
Step 4: a [b c a] b c b b     → window: "bca", max: 3
Step 5: a b [c a b] c b b     → window: "cab", max: 3
Step 6: a b c [a b c] b b     → window: "abc", max: 3
Step 7: a b c a [b c b] b     → duplicate 'b' found, shrink
Step 8: a b c a b [c b] b     → duplicate 'b' found, shrink

The brackets [] represent the current window. Notice how the window never expands beyond length 3 in this case, and the left edge keeps jumping forward when duplicates appear.

Time and Space Complexity Analysis

Time complexity: O(n) — Each character is visited at most twice: once by the right pointer when it enters the window, and once by the left pointer when it leaves. This is the hallmark of the sliding window technique.

Space complexity: O(min(m, n)) — The hash map stores at most the number of unique characters. For ASCII strings, that's at most 128 entries. For Unicode, it could be larger, but it's still bounded by the character set size.

Why use a hash map instead of a hash set? Because the map stores indices, not just presence. This allows the left pointer to jump directly to the position after the previous occurrence, rather than incrementing one step at a time. In the worst case (all identical characters), the set-based approach would still be O(n), but the map-based approach is more efficient in practice.

---

Multi-Language Implementation: Python, Java, JavaScript, C++, and Go

Python Solution

Python's dictionary makes this implementation remarkably clean. I particularly like using enumerate() to get both index and character in one go.

def length_of_longest_substring(s: str) -> int:
    char_index = {}  # Store the most recent index of each character
    left = 0
    max_length = 0
    
    for right, char in enumerate(s):
        # If we've seen this character before and it's in the current window
        if char in char_index and char_index[char] >= left:
            left = char_index[char] + 1
        
        char_index[char] = right
        max_length = max(max_length, right - left + 1)
    
    return max_length

The dict.get() method offers an alternative that some developers prefer:

def length_of_longest_substring(s: str) -> int:
    char_index = {}
    left = 0
    max_length = 0
    
    for right, char in enumerate(s):
        # Using get() with a default value avoids the explicit 'in' check
        prev_index = char_index.get(char, -1)
        if prev_index >= left:
            left = prev_index + 1
        
        char_index[char] = right
        max_length = max(max_length, right - left + 1)
    
    return max_length

Java Solution

Java requires a bit more boilerplate, but the logic translates directly. One thing to watch: autoboxing when working with HashMap<Character, Integer>.

class Solution {
    public int lengthOfLongestSubstring(String s) {
        Map<Character, Integer> charIndex = new HashMap<>();
        int left = 0;
        int maxLength = 0;
        
        for (int right = 0; right < s.length(); right++) {
            char currentChar = s.charAt(right);
            
            // Check if we've seen this character and it's in the current window
            if (charIndex.containsKey(currentChar) && charIndex.get(currentChar) >= left) {
                left = charIndex.get(currentChar) + 1;
            }
            
            charIndex.put(currentChar, right);
            maxLength = Math.max(maxLength, right - left + 1);
        }
        
        return maxLength;
    }
}

For better performance with ASCII strings, you can use an integer array instead of a HashMap:

class Solution {
    public int lengthOfLongestSubstring(String s) {
        int[] charIndex = new int[128];  // ASCII character set
        Arrays.fill(charIndex, -1);       // Initialize to -1 (not seen)
        int left = 0;
        int maxLength = 0;
        
        for (int right = 0; right < s.length(); right++) {
            char currentChar = s.charAt(right);
            
            if (charIndex[currentChar] >= left) {
                left = charIndex[currentChar] + 1;
            }
            
            charIndex[currentChar] = right;
            maxLength = Math.max(maxLength, right - left + 1);
        }
        
        return maxLength;
    }
}

JavaScript Solution

JavaScript's Map object works well here. Modern JS with let/const and arrow functions keeps the code concise.

function lengthOfLongestSubstring(s) {
    const charIndex = new Map();
    let left = 0;
    let maxLength = 0;
    
    for (let right = 0; right < s.length; right++) {
        const currentChar = s[right];
        
        // Check if we've seen this character and it's in the current window
        if (charIndex.has(currentChar) && charIndex.get(currentChar) >= left) {
            left = charIndex.get(currentChar) + 1;
        }
        
        charIndex.set(currentChar, right);
        maxLength = Math.max(maxLength, right - left + 1);
    }
    
    return maxLength;
}

One performance note: for very large strings, using a plain object {} with string keys can be faster than Map in some JavaScript engines, but Map is more predictable and handles non-string keys gracefully.

C++ Solution

C++ offers unordered_map for hash-based storage. The performance is excellent, which is why C++ remains popular in competitive programming.

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        unordered_map<char, int> charIndex;
        int left = 0;
        int maxLength = 0;
        
        for (int right = 0; right < s.length(); right++) {
            char currentChar = s[right];
            
            // Check if we've seen this character and it's in the current window
            if (charIndex.find(currentChar) != charIndex.end() && charIndex[currentChar] >= left) {
                left = charIndex[currentChar] + 1;
            }
            
            charIndex[currentChar] = right;
            maxLength = max(maxLength, right - left + 1);
        }
        
        return maxLength;
    }
};

For maximum performance, you can use a fixed-size array when you know the character set is ASCII:

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        vector<int> charIndex(128, -1);
        int left = 0;
        int maxLength = 0;
        
        for (int right = 0; right < s.length(); right++) {
            char currentChar = s[right];
            
            if (charIndex[currentChar] >= left) {
                left = charIndex[currentChar] + 1;
            }
            
            charIndex[currentChar] = right;
            maxLength = max(maxLength, right - left + 1);
        }
        
        return maxLength;
    }
};

Go Solution

Go's simplicity shines here. No classes, just functions and maps. The map[byte]int type works perfectly for ASCII strings.

func lengthOfLongestSubstring(s string) int {
    charIndex := make(map[byte]int)
    left := 0
    maxLength := 0
    
    for right := 0; right < len(s); right++ {
        currentChar := s[right]
        
        // Check if we've seen this character and it's in the current window
        if prevIndex, exists := charIndex[currentChar]; exists && prevIndex >= left {
            left = prevIndex + 1
        }
        
        charIndex[currentChar] = right
        if right-left+1 > maxLength {
            maxLength = right - left + 1
        }
    }
    
    return maxLength
}

Go's growing popularity in backend engineering makes this a valuable addition to your interview prep toolkit.

---

Handling Edge Cases and Common Pitfalls

Empty String and Single Character

The algorithm handles these naturally:

• "" → The loop never executes, max_length stays 0. ✓
• "a" → One iteration, window is "a", max_length becomes 1. ✓

No special handling needed, but it's worth verifying your implementation doesn't crash on these inputs.

All Unique Characters vs. All Identical Characters

All unique (e.g., "abcdef"): The left pointer never moves because no duplicates are ever found. The window keeps expanding until it covers the entire string. Result: 6. ✓

All identical (e.g., "aaaa"): Every new character is a duplicate. The left pointer jumps to previous_index + 1 each time, so the window never grows beyond size 1. Result: 1. ✓

Let me trace through "aaaa":

Unicode and Special Characters

Here's where things get interesting. Python handles Unicode natively — strings are sequences of Unicode code points, so emojis and accented characters work without any extra effort.

Java and C++ are different stories. In Java, char is a 16-bit UTF-16 code unit. Characters outside the Basic Multilingual Plane (like most emojis) are represented as surrogate pairs — two char values. If you're not careful, your algorithm might treat a single emoji as two separate characters.

In C++, char is typically 8 bits, which only covers ASCII. For Unicode, you'd need wchar_t or a library like ICU.

For most coding interviews, ASCII input is assumed. But if you're building production software that handles international text, you need to think about these encoding issues. In Python, you're safe. In Java, consider using codePointAt() instead of charAt(). In C++, consider using std::wstring or a Unicode library.

---

Beyond LeetCode: Real-World Applications and Variations

Real-World Use Cases

This problem isn't just an interview exercise. I've encountered variations of it in production systems:

Data deduplication in streaming systems: When processing network packets or log streams, you might need to find the longest sequence of unique data items. The sliding window approach works in real-time, processing each item as it arrives.

Text analysis for plagiarism detection: Identifying the longest unique phrase in a document can help detect copied content. The sliding window gives you an efficient way to scan large documents.

Bioinformatics: Finding the longest unique subsequence in DNA sequences is a related problem. While DNA has only 4 characters (A, C, G, T), the sequences can be millions of characters long, making the O(n) sliding window essential.

Problem Variations and Follow-Up Questions

Interviewers love to ask follow-up questions. Here are common variations:

Longest substring with at most K distinct characters: Instead of no repeats, allow up to K distinct characters. The sliding window still works — you just track the number of distinct characters instead of checking for duplicates.

Longest substring with at least K repeating characters: Find the longest substring where every character appears at least K times. This requires a different approach — you need to track character frequencies and check if all characters meet the threshold.

Return the actual substring, not just its length: Simple modification — track the left and right indices when you find a new maximum, then return s[left:right+1].

Handle a stream of characters (online algorithm): What if characters arrive one at a time and you need to maintain the longest unique substring at any point? The sliding window adapts naturally — just process each character as it arrives.

---

FAQ

What is the time complexity of the sliding window solution for the longest substring without repeating characters?

The time complexity is O(n), where n is the length of the string. Each character is processed at most twice: once when the right pointer expands the window to include it, and once when the left pointer shrinks the window to exclude it. This is what makes the sliding window approach so efficient — it's a single pass through the string with constant-time operations at each step.

How do you handle edge cases like an empty string or a string with all identical characters?

The algorithm handles these cases naturally without special-casing. For an empty string, the loop never executes, and the function returns 0. For a string with all identical characters (e.g., "aaaa"), the left pointer moves to previous_index + 1 every time a duplicate is found, so the window never grows beyond size 1, and the function returns 1. The key is ensuring your implementation correctly checks that the previous occurrence is within the current window — not just that the character has been seen before.

Can the longest substring without repeating characters be solved using dynamic programming?

Yes, but it's not the most efficient approach. A dynamic programming solution would involve a 2D table where dp[i][j] represents whether the substring from index i to j has all unique characters. This leads to O(n²) time and space complexity. The sliding window is preferred because it achieves O(n) time and O(min(m, n)) space — a significant improvement for large inputs.

What is the difference between a substring and a subsequence in this context?

A substring is a contiguous sequence of characters within a string — the characters must appear consecutively. A subsequence is a sequence that can be derived by deleting some or no elements without changing the order of the remaining elements — characters can be skipped. For example, in "abc", the substrings are "a", "b", "c", "ab", "bc", and "abc". But "ac" is a subsequence, not a substring. This problem specifically asks for a substring, which is why the sliding window technique works so well.

---

Conclusion

We've covered a lot of ground. Let me recap the key takeaways:

The longest substring without repeating characters problem is a fundamental coding interview question that tests your understanding of data structures, string manipulation, and algorithmic optimization. The brute force approach — generating all substrings and checking each one — works but runs in O(n³) time. The optimal solution uses the sliding window algorithm with a hash map, achieving O(n) time complexity by processing each character at most twice.

We've implemented the solution in five languages — Python, Java, JavaScript, C++, and Go — and discussed how to handle edge cases like empty strings, all-unique strings, and Unicode characters. We've also explored real-world applications and common variations that interviewers might ask as follow-ups.

The sliding window technique is one of the most versatile patterns in algorithm design. Master it here, and you'll recognize it in dozens of other problems.

Ready to test your skills? Head over to LeetCode and try solving "Longest Substring Without Repeating Characters" (Problem #3) on your own. Then, come back and check your solution against our implementations. For more algorithm breakdowns, subscribe to our newsletter!