Longest Substring Without Repeating Characters – Sliding Window Analysis and Optimizations

In the previous section we used a deque to solve a sliding‑window problem; this section delves deeper into pattern‑based sliding‑window problems, focusing on the classic “Longest Substring Without Repeating Characters”.

Most sliding‑window questions test string matching; given a pattern B and a target A, we need to find substrings of A that satisfy certain constraints, e.g., anagrams of B, minimum window containing all characters of T, concatenation of a list of words, etc. The common solution is to maintain a variable‑length window using two pointers, a deque, or a cursor.

Example problem: given a string s, find the length of the longest substring without repeating characters. Sample inputs and outputs are shown.

Analysis: using a set and two pointers we can expand the window when the next character is unseen and shrink it when a duplicate appears. The Java implementation is shown below.

public class Solution {
    public static int lengthOfLongestSubstring(String s) {
        int n = s.length();
        Set<Character> set = new HashSet<>();
        int result = 0, left = 0, right = 0;
        while (left < n && right < n) {
            if (!set.contains(s.charAt(right))) {
                set.add(s.charAt(right));
                right++;
                result = Math.max(result, right - left);
            } else {
                set.remove(s.charAt(left));
                left++;
            }
        }
        return result;
    }
}

The above algorithm visits each character at most twice, yielding O(2N) time. To improve, we can store character‑to‑index mapping in a hashmap, allowing immediate jumps over duplicated characters.

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

Further optimization replaces the hashmap with a fixed‑size array (size 256) for ASCII characters, enabling direct indexing and reducing constant factors.

public class Solution {
    public static int lengthOfLongestSubstring(String s) {
        int len = s.length();
        int result = 0;
        int[] charIndex = new int[256];
        for (int right = 0, left = 0; right < len; right++) {
            char c = s.charAt(right);
            left = Math.max(charIndex[c], left);
            result = Math.max(result, right - left + 1);
            charIndex[c] = right + 1;
        }
        return result;
    }
}

These successive refinements illustrate how sliding‑window techniques evolve from a naïve set‑based approach to hashmap‑based and finally to array‑based implementations, achieving optimal O(N) time with minimal overhead.