Q13: How do you find the length of the Longest Substring Without Repeating Characters using Sliding Window?

Maintain a dynamic Sliding Window bounded by left and right pointers, along with a HashMap<Character, Integer> mapping characters to their most recent index. As right scans forward, if a duplicate character is found at index $ge left$, jump left = map.get(char) + 1. Calculate maxLength = Math.max(maxLength, right - left + 1).

Sliding Window Substring Solution

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

public class LongestSubstring {
    public static int lengthOfLongestSubstring(String s) {
        Map<Character, Integer> map = new HashMap<>();
        int maxLength = 0, left = 0;
        for (int right = 0; right < s.length(); right++) {
            char c = s.charAt(right);
            if (map.containsKey(c)) {
                left = Math.max(left, map.get(c) + 1);
            }
            map.put(c, right);
            maxLength = Math.max(maxLength, right - left + 1);
        }
        return maxLength;
    }
}

💡 Jumps the left window boundary past duplicate characters using hash index tracking.

Key Takeaways

Sliding Window with fast pointer jumping via index lookup maps.
Achieves $O(n)$ time complexity in a single pass.

Knowledge Check

Why is left updated using left = Math.max(left, map.get(c) + 1) rather than left = map.get(c) + 1 directly?

Q13: How do you find the length of the Longest Substring Without Repeating Characters using Sliding Window?

STAY UPDATED WITH BYTES!