Longest Substring Without Repeating Characters

1. Defining the Problem

The problem statement is concise but requires careful thought. Given a string, our goal is to find the length of the longest substring that contains no repeating characters.

Let's break this down with a few examples:

• Input: s = "abcabcbb" -> Output: 3 (The longest substring is "abc").
• Input: s = "bbbbb" -> Output: 1 (The longest substring is "b").
• Input: s = "pwwkew" -> Output: 3 (The longest substring is "wke". Note that "pwke" is a subsequence, not a substring, as it's not contiguous).

This problem is a staple in technical interviews because it effectively tests your ability to recognize patterns, choose appropriate data structures, and optimize your solution—all critical skills for a software development role.

2. Approach 1: The Brute-Force Solution

Let's begin with the most intuitive approach. The problem asks for the longest valid substring. A straightforward way to tackle this is to generate every single possible substring, check if it contains unique characters, and keep track of the length of the longest valid one we find.

How can we implement this?

1. Use a pair of nested loops to generate all substrings. The outer loop (i) picks a starting character, and the inner loop (j) picks an ending character.
2. For each generated substring s[i...j], we need a helper function to verify if all its characters are unique. This helper can use a HashSet to efficiently check for duplicates. If we encounter a character that's already in our set for the current substring, it's not unique.
3. If the substring is indeed unique, we compare its length (j - i + 1) with our current maximum length and update it if necessary.

This method is thorough but, as we'll see, computationally expensive.

(Note: A slightly more optimized O(n²) brute-force can be written, as seen in the GeeksforGeeks article, but the core idea of checking all substrings remains inefficient.)

3. A Better Approach: Sliding Window with a HashSet

The brute-force method is slow because it repeatedly re-evaluates overlapping substrings. The sliding window technique offers a way to avoid this. We can maintain a "window" representing our current substring of unique characters and slide it across the string.

Here, the window size is not fixed. It expands when we find a new unique character and shrinks when we encounter a duplicate.

Here is the logic using two pointers, left and right, and a HashSet:

1. Initialize left = 0, right = 0, maxLength = 0, and an empty HashSet.
2. Iterate with the right pointer from the beginning to the end of the string, expanding the window.
3. For each character s.charAt(right), check if it's already in the HashSet.
   • If it's a duplicate: The window [left, right] is now invalid. We must shrink the window from the left. In a while loop, remove s.charAt(left) from the set and increment left until the duplicate is no longer in the set.
   • If it's unique: The character is fine.
4. Add the current character s.charAt(right) to the HashSet.
5. At this point, the window [left, right] is guaranteed to contain unique characters. Update the max length: maxLength = Math.max(maxLength, right - left + 1).

This approach ensures that each character is processed at most twice (once by right and once by left), leading to a linear time complexity.

4. The Optimal Approach: Sliding Window with a HashMap or Array

We can optimize further. The HashSet approach shrinks the window one character at a time from the left. What if we could jump the left pointer directly to the correct position?

We can achieve this by using a HashMap<Character, Integer> to store not just the character, but its last seen index.

The logic is refined as follows:

1. Initialize left = 0, right = 0, maxLength = 0, and an empty HashMap.
2. Iterate with the right pointer from 0 to n-1.
3. When considering the character c = s.charAt(right):
   • Check if c is in the HashMap.
   • If it is, it's a potential duplicate. Let its last seen index be lastIndex = map.get(c). We must ensure our left pointer is past this last occurrence. However, we only care if this lastIndex falls within our current window (lastIndex >= left). So, we update left = Math.max(left, lastIndex + 1). This Math.max is a key trick to prevent left from ever moving backward.
4. Update the character's last seen index in the map: map.put(c, right).
5. Calculate the current window's length and update the max: maxLength = Math.max(maxLength, right - left + 1).

Striver provides an excellent, detailed dry run of this exact logic in his video. Watching this will solidify your understanding of how the pointers and the map interact.

The image below illustrates this jumping mechanism. When the right pointer encounters the second 'a' (at index 5), the left pointer doesn't just move one step; it jumps to index 1, which is one position after the previous 'a' was seen.

Here is the Java code for this optimal approach.

A Final Optimization: Using an Array

If we know the character set is limited (e.g., ASCII, which has 128 or 256 characters), we can replace the HashMap with a simple integer array of size 128 or 256. The character's ASCII value serves as the index. This is slightly more performant as it avoids the overhead of hashing and potential hash collisions. The logic remains identical.

You can find the Java code for this array-based optimization in the same Medium article under "Solution 4: Array-Based Sliding Window". For most interviews, the HashMap solution is perfectly optimal and more general, but mentioning this array-based optimization demonstrates a deeper level of performance awareness.

Conclusion

In this lesson, we advanced from the fixed-size sliding window to the more versatile variable-size window. We tackled a classic interview problem, progressing from a naive brute-force method to a highly efficient linear-time solution, a thought process highly valued by interviewers.

Key Takeaways:

• Variable-Size Window: This pattern is ideal for finding the longest/shortest substring/subarray that satisfies a certain condition. The window expands and shrinks dynamically.
• Problem: Longest Substring Without Repeating Characters.
• Brute-Force: O(n³) or O(n²) complexity by checking all substrings. Too slow for interviews.
• Better Solution (HashSet): An O(n) sliding window approach where the window shrinks from the left by one element at a time to resolve duplicates.
• Optimal Solution (HashMap/Array): A true O(n) single-pass sliding window where the left pointer intelligently jumps forward to resolve duplicates, avoiding incremental shrinking.
• Data Structures: A HashSet is good for checking presence, while a HashMap or an integer array is better for the optimal solution as it can store the last-seen index.

In our next lesson, we will continue with the variable-size sliding window pattern and apply it to another challenging and common interview problem: finding the "Minimum Window Substring". This will add another layer of complexity and further cement your understanding of this powerful technique.