↔️

Variable (Dynamic) Sliding Window

Window size is not fixed. Expand right to grow; when constraint violated, shrink from left until valid again. Track the best window seen.

Array String Time O(n) Space O(k) map

📋 When to Use

Find longest / shortest subarray or substring meeting a constraint
Constraint involves distinct elements or char frequencies
Shrinking from left is always valid (monotonicity holds)
Min window, longest no-repeat, max consecutive ones, anagram

💡 Three-step loop: ① EXPAND R right, ② SHRINK L right while invalid, ③ UPDATE best. Each element enters and exits at most once → O(n).

⚡ Complexity

Time

O(n)

Space

O(k)

Each element is processed at most twice (once by R, once by L). The map holds at most k unique elements where k = alphabet size or distinct elements.

For ASCII strings: effectively O(1) space since k ≤ 128.

Problem Given a string s, find the length of the longest substring that contains no duplicate characters. Use a HashMap to track character counts — expand right to add chars, shrink left whenever a duplicate appears.
Input: s = "pwwkew" · Answer: 3 (substring "wke", indices 2–4)

Step 1 / —

➡ EXPAND (R →)

⬅ SHRINK (← L)

★ UPDATE best

✅ Done

R entering (expand)

L leaving (shrink)

Window contents

Best window

s = "p w w k e w"

L = —

R = —

len = —

result = 0

Window Contents (char → count)

empty

Click ▶ Play or Next ▶ to begin.

int left = 0, result = 0; Map<Character,Integer> window = new HashMap<>();

Complete Java TemplateJAVA

int longestSubstringNoRepeat(String s) {
    int left = 0, result = 0;
    Map<Character, Integer> window = new HashMap<>();

    for (int right = 0; right < s.length(); right++) {

        // ① EXPAND — add s[right] into window
        window.merge(s.charAt(right), 1, Integer::sum);

        // ② SHRINK — while duplicate exists, remove from left
        while (window.get(s.charAt(right)) > 1) {
            window.merge(s.charAt(left), -1, Integer::sum);
            if (window.get(s.charAt(left)) == 0)
                window.remove(s.charAt(left));
            left++;
        }

        // ③ UPDATE — record best window length
        result = Math.max(result, right - left + 1);
    }
    return result;   // O(n) — each char enters and exits at most once
}

🎯 Practice Problems

#3Longest Substring Without Repeating CharactersMedium #209Minimum Size Subarray SumMedium #1004Max Consecutive Ones III — at most k zerosMedium #424Longest Repeating Character ReplacementMedium #567Permutation in StringMedium #438Find All Anagrams in a StringMedium #76Minimum Window Substring — hardest dynamic windowHard