Longest Substring Without Repeating Characters medium

Problem Statement

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

Example 1

Input: s = "abcabcbb" Output: 3 Explanation: The answer is "abc", with the length of 3.

Example 2

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

Steps

1. Initialization: We'll use a HashMap to store the characters and their last seen indices. We also need two pointers, left and right, both initially at 0. maxLength will store the maximum length found so far.

2. Sliding Window: We iterate using the right pointer. For each character:

   • Check if the character is already in the HashMap.
   • If it's not in the HashMap, it's a new character, so add it to the HashMap with its index. Update maxLength if the current window size (right - left + 1) is greater.
   • If it's already in the HashMap, it means we have a repeating character. We need to shrink the window. Move the left pointer to the index after the last seen index of the repeating character. Update the character's index in the HashMap to the current right index.

3. Return: After iterating through the entire string, maxLength will hold the length of the longest substring without repeating characters.

Explanation

The algorithm uses a sliding window approach. The window expands with the right pointer and contracts with the left pointer. The HashMap efficiently tracks the last seen index of each character. When a repeating character is encountered, the window contracts to exclude the first occurrence of that character. This ensures that at any given time, the window contains only unique characters.

Code

import java.util.HashMap;

class Solution {
    public int lengthOfLongestSubstring(String s) {
        HashMap<Character, Integer> charIndexMap = new HashMap<>();
        int left = 0;
        int right = 0;
        int maxLength = 0;

        while (right < s.length()) {
            char currentChar = s.charAt(right);

            if (!charIndexMap.containsKey(currentChar)) {
                charIndexMap.put(currentChar, right);
                maxLength = Math.max(maxLength, right - left + 1);
                right++;
            } else {
                int lastSeenIndex = charIndexMap.get(currentChar);
                left = Math.max(left, lastSeenIndex + 1); // Move left pointer past the repeated char
                charIndexMap.put(currentChar, right); //Update the index of the repeated char
                right++;
            }
        }
        return maxLength;
    }
}

Complexity

• Time Complexity: O(n), where n is the length of the string. In the worst case, we iterate through the string once.
• Space Complexity: O(min(m, n)), where n is the length of the string and m is the size of the character set (number of unique characters). In the worst case (all unique characters), the HashMap will store all characters. If the number of unique characters is small compared to the string length, the space complexity could be considered O(m).