Longest Substring Without Repeating Characters

Given a string s, find the length of the longest substring without duplicate characters.

Example 1:

Input: s = “abcabcbb” Output: 3 Explanation: The answer is “abc”, with the length of 3. Note that "bca" and "cab" are also correct answers.

Example 2:

Input: s = “bbbbb” Output: 1 Explanation: The answer is “b”, with the length of 1.

Example 3:

Input: s = “pwwkew” Output: 3 Explanation: The answer is “wke”, with the length of 3. Notice that the answer must be a substring, “pwke” is a subsequence and not a substring.

Constraints:

• 0 <= s.length <= 105
• s consists of English letters, digits, symbols and spaces.

Approach: Sliding Window with HashMap (Optimal Solution)

Algorithm

1. Use two pointers (left and right) to define the current window
2. Use a hash map to store each character and its most recent index
3. Expand right through the string
4. If the current character is already in the map and its index is within the window, move left to index + 1
5. Update the character’s latest index in the map
6. Track the maximum window size (right - left + 1)

Key Insight

When a duplicate character is found inside the current window, the window cannot start before the previous occurrence of that character. By sliding left past it, we only ever expand or shift the window, never shrinking below the current best.

Time & Space Complexity

• Time Complexity: O(n) - single pass through the string
• Space Complexity: O(min(m, n)) - hash map stores at most the distinct characters in the window

Java Implementation

import java.util.HashMap;
import java.util.Map;

public class LongestSubstringWithoutRepeatingCharacters {

    /**
     * Find the length of the longest substring without repeating characters.
     * @param s Input string
     * @return Length of the longest substring without duplicate characters
     */
    public static int lengthOfLongestSubstring(String s) {
        Map<Character, Integer> charMap = new HashMap<>();
        int maxLength = 0;
        int left = 0;

        for (int right = 0; right < s.length(); right++) {
            char c = s.charAt(right);

            // If character is a duplicate within the current window, move left
            if (charMap.containsKey(c) && charMap.get(c) >= left) {
                left = charMap.get(c) + 1;
            }

            // Update the character's latest index
            charMap.put(c, right);

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

        return maxLength;
    }

    // Test method
    public static void main(String[] args) {
        // Test case 1
        System.out.println("Input: s = \"abcabcbb\"");
        System.out.println("Output: " + lengthOfLongestSubstring("abcabcbb")); // Expected: 3

        // Test case 2
        System.out.println("Input: s = \"bbbbb\"");
        System.out.println("Output: " + lengthOfLongestSubstring("bbbbb")); // Expected: 1

        // Test case 3
        System.out.println("Input: s = \"pwwkew\"");
        System.out.println("Output: " + lengthOfLongestSubstring("pwwkew")); // Expected: 3
    }
}

Example Walkthrough

For s = "abcabcbb":

1. right=0, c=‘a’: window=[a], left=0, maxLength=1
2. right=1, c=‘b’: window=[ab], left=0, maxLength=2
3. right=2, c=‘c’: window=[abc], left=0, maxLength=3
4. right=3, c=‘a’: ‘a’ at index 0 in window, left=1, window=[bca], maxLength=3
5. right=4, c=‘b’: ‘b’ at index 1 in window, left=2, window=[cab], maxLength=3
6. right=5, c=‘c’: ‘c’ at index 2 in window, left=3, window=[abc], maxLength=3
7. right=6, c=‘b’: ‘b’ at index 4 in window, left=5, window=[b], maxLength=3
8. right=7, c=‘b’: ‘b’ at index 6 in window, left=7, window=[b], maxLength=3

Maximum length = 3

Alternative Brute Force Approach (Less Efficient)

public static int lengthOfLongestSubstringBruteForce(String s) {
    int maxLength = 0;

    for (int i = 0; i < s.length(); i++) {
        Set<Character> seen = new HashSet<>();
        for (int j = i; j < s.length(); j++) {
            if (seen.contains(s.charAt(j))) {
                break;
            }
            seen.add(s.charAt(j));
            maxLength = Math.max(maxLength, j - i + 1);
        }
    }

    return maxLength;
}

Key Insights

1. Sliding Window: Maintains a window of non-repeating characters using two pointers
2. HashMap: Tracks the latest index of each character for O(1) duplicate detection
3. Single Pass: Expands right continuously while only moving left forward, giving O(n) time
4. Substring vs Subsequence: Ensures the result is contiguous, unlike a subsequence

The sliding window approach is the optimal solution for this problem, providing linear time complexity.