Data Structures & Algorithms (Sliding Window): 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.

Solve Here: Leetcode 3

Approach 1: Explore the Longest Substring Starting from Each Index

Use nested loops to explore longest possible substring starting from each character.

For each starting index, expand the substring one character at a time while maintaining a HashSet to track visited characters. If a duplicate character is encountered, stop expanding further for that starting index and move to the next index.

Algorithm

public int lengthOfLongestSubstring(String s) {

    int maxLength = Integer.MIN_VALUE;

    for(int i = 0; i < s.length(); i++) {
        Set<Character> unique = new HashSet<>();
        int currLength = 0;
        for(int j = i; j < s.length(); j++) {
            char ch = s.charAt(j);
            if(!unique.contains(ch)) {
                unique.add(ch);
                currLength++;
                maxLength = Math.max(maxLength, currLength);
            } else {
                break;
            }
        }
    }

    return maxLength == Integer.MIN_VALUE ? 0 : maxLength;

}

Visualization

Time Complexity

In the worst-case scenario (all characters in the input string are unique), for every starting index i, we explore all (n-i) ending indices to its right.

This results in a total of: n + (n-1) + ... + 2 + 1 = n(n+1)/2 iterations of the inner loop across all starting indices.

Therefore, the overall time complexity = O(n²).

Space Complexity

We use a HashSet to store the characters in the current substring. In the worst case (when all characters are unique), the set can grow to hold at most n characters at a time.

Therefore, the overall space complexity = O(n).

Key Observation

While expanding a substring, if we encounter a character that has already been seen, we can directly move the starting index i to the position right after the previous occurrence of that character.

Any starting index before that would only produce smaller substrings.

NOTE: A character is only considered duplicate only if its previous occurrence lies within the current window. If it appears before the current starting index, it can be safely ignored.

Approach 2: Expand & Shrink

Use two pointers (i, j) to traverse the string while maintaining a sliding window.

• Expland the window (j++) when the current character is not duplicate withing the current window.

• If a duplicate character is encountered, shrink the window by moving i forward until the duplicate is removed.

NOTE: Maintain a HashMap to store the last seen index of each character. This allows you to efficiently jump i forward to lastSeenIndex + 1, instead of moving it step by step.

Algorithm

public int lengthOfLongestSubstring(String s) {

    int maxLength = Integer.MIN_VALUE;
    Map<Character, Integer> lastSeen = new HashMap<>();
    
    int i = 0;
    for(int j = 0; j < s.length(); j++) {

        char ch = s.charAt(j);

        // If duplicate, shrink the window
        if(lastSeen.containsKey(ch) && lastSeen.get(ch) >= i) {
            i = lastSeen.get(ch) + 1;
        }

        // Persist current character index 
        lastSeen.put(ch, j);

        maxLength = Math.max(maxLength, j - i + 1);

    }

    return maxLength == Integer.MIN_VALUE ? 0 : maxLength;

}

Visualization

Time Complexity

Each character is visited at most twice, once when the right pointer expands the window and once when the left pointer shrinks it.

Since both pointers traverse the string at most n times, the overall time complexity = O(n).

Space Complexity

The HashMap stores the last seen index of each unique character. In the worst case (when all characters are distinct), it can hold up to n entries.

Therefore, the overall space complexity = O(n).