Sliding Window Dynamic Size

This algorithmic technique is used when we need to handle the input data in a window size. Unlike the Sliding Window Fixed Size , this technique does NOT have a size constraint. The window size grows or shrinks as it moves along the data structure.

How to Identify

• Data Structure Involves: Array, String, Linked List
• Question Type: Find the maximum/minimum/longest/shortest substring, subarray, or a target value in a linear data structure such as a linked list, array, or string.

Example

Longest Substring Without Repeating Characters

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

Example

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

Typescript

function lengthOfLongestSubstring(s: string): number {
    let charTable: { [key: string]: number } = {}
    let start = 0, maxLength = 0

    for(let end = 0; end < s.length; end++){
        let char = s[end]

        if(char in charTable && start <= charTable[char]){
            start = charTable[char] + 1
        }

        charTable[char] = end
        maxLength = Math.max(maxLength, end - start + 1)
    }

    return maxLength
};

Related Problems

	Problems	Difficulty
1	Minimum Size Subarray Sum	Medium
2	Longest Substring Without Repeating Characters	Medium
3	Longest Repeating Character Replacement	Medium
4	Minimum Window Substring	Hard
5	Sliding Window Maximum	Hard