Question 3

Longest Substring Without Repeating Characters

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

Approach: Sliding Window

To solve this problem efficiently, we can use a sliding window approach. This technique involves maintaining a "window" of characters within the string that does not contain any duplicates. As we iterate through the string, we adjust the window size to maximize the length of the substring with unique characters.

Steps

1. Initialize Pointers and Data Structures:

   • Use two pointers, left and right, to represent the current window in the string s.
   • Use a set to keep track of characters in the current window. This will help in checking duplicates efficiently.
   • Initialize max_length to store the length of the longest substring without repeating characters.

2. Expand and Contract the Window:

   • Iterate over the string with the right pointer, adding each character to the set.
   • If a duplicate character is found in the set, move the left pointer to the right until there are no duplicates in the current window.
   • Update max_length with the current window size if it’s greater than the previous maximum.

3. End Condition:

   • The loop ends when the right pointer has iterated through the string.
   • max_length will contain the length of the longest substring without repeating characters.

4. Time Complexity:

   • O(n), where n is the length of the string s. Both left and right pointers traverse the string at most once.

Code

Here’s the Java implementation:

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

public class Solution {
    public int lengthOfLongestSubstring(String s) {
        // Set to store characters in the current window
        Set<Character> charSet = new HashSet<>();
        
        // Pointers for the sliding window
        int left = 0;
        int maxLength = 0;
        
        // Loop through each character with the 'right' pointer
        for (int right = 0; right < s.length(); right++) {
            // If a duplicate is found, move the 'left' pointer to the right
            // until there are no duplicates in the current window
            while (charSet.contains(s.charAt(right))) {
                charSet.remove(s.charAt(left));
                left++;
            }
            
            // Add the character at 'right' to the set (current window)
            charSet.add(s.charAt(right));
            
            // Update the max length of the substring without duplicates
            maxLength = Math.max(maxLength, right - left + 1);
        }
        
        return maxLength;
    }
}