Finding the Length of the Longest Substring Without Repeating Characters

In this post, we will solve this popular coding interview question using sliding window pattern.

Problem Statement

Given a string s, you need to find the length of the longest substring that contains no repeating characters.

A substring is a contiguous sequence of characters within a string. The main objective is to identify the longest possible substring without any character repetition and return its length.

Examples

Let’s go through a few examples to understand the expected input and output:

Example 1:

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

Example 2:

• Input: s = "bbbbb"
• Output: 1
• Explanation: The longest substring without repeating characters is "b" with a length of 1.

Example 3:

• Input: s = "pwwkew"
• Output: 3
• Explanation: The longest substring without repeating characters is "wke". Note that the answer must be a substring, "pwke" is not a substring as it is not contiguous.

Example 4 (Edge Case):

• Input: s = ""
• Output: 0
• Explanation: The input string is empty, so the length of the longest substring is 0.

Example 5:

• Input: s = " "
• Output: 1
• Explanation: The input string contains only one character (a space), so the length is 1.

Brute Force Approach

The brute force approach involves checking every possible substring of s and determining if it has all unique characters. We would then keep track of the maximum length of substrings without repeating characters.

To check if a substring has all unique characters, we can use a data structure like a Set.

Steps

1. Generate all possible substrings of s.
2. For each substring, check if all characters are unique.
3. Track the length of the longest substring with unique characters.
4. Return the maximum length found.

Time and Space Complexity

• Time Complexity: O(N³), where N is the length of the string s. Generating all substrings takes O(N²) time, and checking if each substring has all unique characters takes O(N) time in the worst case.
• Space Complexity: O(N), as we may use a set to store characters of a substring.

Brute Force Code in Java

Here is the implementation of the brute force approach in Java for reference.

Note: In a real interview, it is not a good idea to write code for brute force approach, just explain the time and space complexity of the brute force approach and move on to the optimal solution.

public class LongestSubstringBruteForce {

    public static int lengthOfLongestSubstringBruteForce(String s) {
        int maxLength = 0; // Variable to store the maximum length

        // Iterate over all possible substrings
        for (int i = 0; i < s.length(); i++) {
            for (int j = i; j < s.length(); j++) {
                if (allUnique(s, i, j)) {
                    maxLength = Math.max(maxLength, j - i + 1);
                }
            }
        }

        return maxLength; 
    }

    // Helper function to check if all characters in the substring are unique
    private static boolean allUnique(String s, int start, int end) {
        Set<Character> set = new HashSet<>();
        for (int i = start; i <= end; i++) {
            char ch = s.charAt(i);
            if (set.contains(ch)) {
                return false; // Character is repeated
            }
            set.add(ch);
        }
        return true; // All characters are unique
    }

    public static void main(String[] args) {
        String test1 = "abcabcbb";
        String test2 = "bbbbb";
        String test3 = "pwwkew";
        String test4 = "";
        String test5 = " ";

        System.out.println("Brute Force - Length of Longest Substring: " + lengthOfLongestSubstringBruteForce(test1)); // Output: 3
        System.out.println("Brute Force - Length of Longest Substring: " + lengthOfLongestSubstringBruteForce(test2)); // Output: 1
        System.out.println("Brute Force - Length of Longest Substring: " + lengthOfLongestSubstringBruteForce(test3)); // Output: 3
        System.out.println("Brute Force - Length of Longest Substring: " + lengthOfLongestSubstringBruteForce(test4)); // Output: 0
        System.out.println("Brute Force - Length of Longest Substring: " + lengthOfLongestSubstringBruteForce(test5)); // Output: 1
    }
}

Optimal Approach: Sliding Window Technique

We can use Sliding Window approach to solve this problem efficiently in O(N) time complexity. We can either use HashSet or HashMap data structure to help keep track of repeating characters. Let’s look at both the variations.

Sliding Window Technique Illustration

Using HashSet

Let’s use HashSet to track the characters. We use two pointers (left and right) to represent the current window of characters without duplicates.

As we slide the window across the string:

1. Expand the window by moving the right pointer to include new characters.
2. If a duplicate character is encountered, move the left pointer to the right until all characters in the window are unique again.
3. Track the maximum window size during this process.

Steps:

1. Initialize two pointers (left and right) and a Set to keep track of characters in the current window.
2. Expand the window by moving the right pointer.
3. If the character at right is not in the set, add it to the set and update the maximum length.
4. If the character is already in the Set, remove characters from the left of the window until the duplicate is removed.
5. Repeat until the right pointer reaches the end of the string.

Java Code

import java.util.HashSet;
import java.util.Set;

public class LongestSubstringOptimal {

    // Function to find the length of the longest substring without repeating characters
    public static int lengthOfLongestSubstringOptimal(String s) {
        int maxLength = 0; // Variable to store the maximum length
        int left = 0; // Left pointer for the sliding window
        Set<Character> set = new HashSet<>(); // Set to store characters in the current window

        // Iterate over the characters using the right pointer
        for (int right = 0; right < s.length(); right++) {
            // If the character at 'right' is a duplicate, shrink the window from the left
            while (set.contains(s.charAt(right))) {
                set.remove(s.charAt(left)); // Remove the character at 'left'
                left++; // Move the left pointer to the right
            }

            // Add the character at 'right' to the set
            set.add(s.charAt(right));

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

        return maxLength; // Return the length of the longest substring without repeating characters
    }

    // Main method to test the optimal approach
    public static void main(String[] args) {
        String test1 = "abcabcbb";
        String test2 = "bbbbb";
        String test3 = "pwwkew";
        String test4 = "";
        String test5 = " ";

        System.out.println("Optimal - Length of Longest Substring: " + lengthOfLongestSubstringOptimal(test1)); // Output: 3
        System.out.println("Optimal - Length of Longest Substring: " + lengthOfLongestSubstringOptimal(test2)); // Output: 1
        System.out.println("Optimal - Length of Longest Substring: " + lengthOfLongestSubstringOptimal(test3)); // Output: 3
        System.out.println("Optimal - Length of Longest Substring: " + lengthOfLongestSubstringOptimal(test4)); // Output: 0
        System.out.println("Optimal - Length of Longest Substring: " + lengthOfLongestSubstringOptimal(test5)); // Output: 1
    }
}

Time and Space Complexity

• Time Complexity: O(N), where N is the length of the string. Each character is processed at most twice (once by the right pointer and at most once by the left pointer).
• Space Complexity: O(M), where M is the size of the character set. This could be up to 256 if all characters in the string are unique.

Using HashMap

The sliding window technique combined with a HashMap provides an even more efficient way to find the length of the longest substring without repeating characters.

Using a HashMap, we can directly map each character to its most recent index, allowing us to quickly move the left pointer of our window whenever a duplicate character is encountered.

The idea is to use a HashMap to keep track of characters and their most recent positions.

When a duplicate character is found within the current window, we can directly move the left pointer to the position after the duplicate's previous occurrence. This allows us to efficiently skip over duplicates without shrinking the window one character at a time.

Steps:

1. Use a HashMap to store characters and their latest indices.
2. Initialize two pointers (left and right), representing the window's bounds.
3. Move the right pointer to expand the window:

• If the current character is already in the map and its index is greater than or equal to left, move the leftpointer to map.get(char) + 1 to skip the duplicate.
• Update the character’s index in the HashMap.
• Calculate the maximum window length.

4. Continue until the right pointer reaches the end of the string.

Java Code

import java.util.HashMap;

public class LongestSubstringWithHashMap {

    public static int lengthOfLongestSubstring(String s) {
        // HashMap to store the last occurrence index of each character
        HashMap<Character, Integer> charIndexMap = new HashMap<>();
        int maxLength = 0; // Maximum length of substring
        int left = 0; // Left pointer for the sliding window

        // Iterate over the characters using the right pointer
        for (int right = 0; right < s.length(); right++) {
            char currentChar = s.charAt(right);

            // If the character is already in the map and its index is within the current window
            if (charIndexMap.containsKey(currentChar) && charIndexMap.get(currentChar) >= left) {
                // Move the left pointer to the right of the last occurrence of the current character
                left = charIndexMap.get(currentChar) + 1;
            }

            // Update the last occurrence index of the current character
            charIndexMap.put(currentChar, right);

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

        return maxLength; // Return the length of the longest substring without repeating characters
    }

    // Main method to test the optimal approach using HashMap
    public static void main(String[] args) {
        String test1 = "abcabcbb";
        String test2 = "bbbbb";
        String test3 = "pwwkew";
        String test4 = "";
        String test5 = " ";

        System.out.println("HashMap - Length of Longest Substring: " + lengthOfLongestSubstring(test1)); // Output: 3
        System.out.println("HashMap - Length of Longest Substring: " + lengthOfLongestSubstring(test2)); // Output: 1
        System.out.println("HashMap - Length of Longest Substring: " + lengthOfLongestSubstring(test3)); // Output: 3
        System.out.println("HashMap - Length of Longest Substring: " + lengthOfLongestSubstring(test4)); // Output: 0
        System.out.println("HashMap - Length of Longest Substring: " + lengthOfLongestSubstring(test5)); // Output: 1
    }
}

Time and Space Complexity

• Time Complexity: O(N), where N is the length of the string. Each character is processed at most once.
• Space Complexity: O(M), where M is the size of the character set, which can be up to 256 for ASCII.

For more such in-depth explanations, problem-solving techniques, and coding interview patterns, consider purchasing the “Handbook for Coding Interviews” available on Amazon.com. This book is a comprehensive guide to acing coding interviews with detailed solutions to the most frequently asked coding interview questions.

If you found this post useful, please follow me on Medium. More to come!