Sliding Window Pattern

Relevant source files

• solution/0000-0099/0002.Add Two Numbers/README.md
• solution/0000-0099/0002.Add Two Numbers/README_EN.md
• solution/0000-0099/0002.Add Two Numbers/Solution.c
• solution/0000-0099/0002.Add Two Numbers/Solution.cpp
• solution/0000-0099/0002.Add Two Numbers/Solution.cs
• solution/0000-0099/0002.Add Two Numbers/Solution.go
• solution/0000-0099/0002.Add Two Numbers/Solution.java
• solution/0000-0099/0002.Add Two Numbers/Solution.js
• solution/0000-0099/0002.Add Two Numbers/Solution.nim
• solution/0000-0099/0002.Add Two Numbers/Solution.py
• solution/0000-0099/0002.Add Two Numbers/Solution.rb
• solution/0000-0099/0002.Add Two Numbers/Solution.rs
• solution/0000-0099/0003.Longest Substring Without Repeating Characters/README.md
• solution/0000-0099/0003.Longest Substring Without Repeating Characters/README_EN.md
• solution/0000-0099/0003.Longest Substring Without Repeating Characters/Solution.cpp
• solution/0000-0099/0003.Longest Substring Without Repeating Characters/Solution.cs
• solution/0000-0099/0003.Longest Substring Without Repeating Characters/Solution.go
• solution/0000-0099/0003.Longest Substring Without Repeating Characters/Solution.java
• solution/0000-0099/0003.Longest Substring Without Repeating Characters/Solution.js
• solution/0000-0099/0003.Longest Substring Without Repeating Characters/Solution.php
• solution/0000-0099/0003.Longest Substring Without Repeating Characters/Solution.py
• solution/0000-0099/0003.Longest Substring Without Repeating Characters/Solution.rs
• solution/0000-0099/0003.Longest Substring Without Repeating Characters/Solution.ts

Purpose and Scope

This page documents the Sliding Window Pattern, a technique for efficiently processing contiguous subsequences (subarrays or substrings) by maintaining a dynamic window with two pointers. The pattern is demonstrated through Problem 0003 (Longest Substring Without Repeating Characters), which finds the maximum-length substring with all unique characters.

For other algorithmic patterns, see Hash Table Pattern, Two Pointers Pattern, and Binary Search Pattern.

Pattern Overview

The sliding window pattern uses two pointers (l and r) to define a window range [l, r] within a sequence. The window expands by moving the right pointer forward and contracts by moving the left pointer forward, maintaining a specific invariant throughout the process.

Common Use Cases:

• Finding optimal contiguous subsequences (longest, shortest, count)
• Tracking element frequencies within a dynamic range
• Substring problems with character constraints
• Fixed-size or variable-size window operations

Key Characteristics:

Aspect	Description
Pointers	Two pointers l (left) and r (right) defining window boundaries
Window Invariant	A condition that must always hold true within [l, r]
Expansion	Right pointer r moves forward to include new elements
Contraction	Left pointer l moves forward to restore the invariant
Time Complexity	Typically O(n) since each element is visited at most twice

Sources: solution/0000-0099/0003.Longest Substring Without Repeating Characters/README.md65-73 solution/0000-0099/0003.Longest Substring Without Repeating Characters/README_EN.md64-71

Algorithm Flow

Algorithm Steps:

1. Initialize two pointers l=0 and r=0, and a frequency counter cnt
2. Expand the window by incrementing r and updating cnt[s[r]]
3. Check invariant: If cnt[s[r]] > 1, the window has duplicates
4. Contract the window by incrementing l and decrementing cnt[s[l]] until the invariant is restored
5. Update the answer with the current window size r - l + 1
6. Repeat steps 2-5 until r reaches the end of the sequence

Sources: solution/0000-0099/0003.Longest Substring Without Repeating Characters/README.md65-71 solution/0000-0099/0003.Longest Substring Without Repeating Characters/README_EN.md64-69

Example Problem: LeetCode 0003

Problem: Longest Substring Without Repeating Characters

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

Examples:

Input	Output	Explanation
"abcabcbb"	3	Substring "abc" has length 3
"bbbbb"	1	Substring "b" has length 1
"pwwkew"	3	Substring "wke" has length 3

Constraints:

• 0 <= s.length <= 5 * 10^4
• String consists of English letters, digits, symbols, and spaces

Sources: solution/0000-0099/0003.Longest Substring Without Repeating Characters/README.md17-58 solution/0000-0099/0003.Longest Substring Without Repeating Characters/README_EN.md17-55

Window State Transitions

Sources: solution/0000-0099/0003.Longest Substring Without Repeating Characters/README.md67-70

Core Implementation Components

Data Structures

The sliding window pattern for problem 0003 uses the following key data structures:

Component	Type	Purpose	Implementation
cnt	Array or Hash Map	Frequency counter for characters in window	int[128] for ASCII or Map<char, int>
l	Integer	Left boundary of window	Initialized to 0
r	Integer	Right boundary of window	Incremented in loop
ans	Integer	Maximum window size found	Updated with max(ans, r - l + 1)

Array vs Hash Map:

• Array (int[128]): Used when character set is bounded (ASCII), provides O(1) access
• Hash Map: Used for flexible character sets, provides O(1) average access

Sources: solution/0000-0099/0003.Longest Substring Without Repeating Characters/Solution.java3-4 solution/0000-0099/0003.Longest Substring Without Repeating Characters/Solution.ts3

Pointer Management

Pointer Movement Rules:

1. Right pointer r: Always increments in the main loop, adding new elements
2. Left pointer l: Increments conditionally in the inner while loop when invariant is violated
3. Window size: Calculated as r - l + 1 after each expansion

Sources: solution/0000-0099/0003.Longest Substring Without Repeating Characters/Solution.py4-10 solution/0000-0099/0003.Longest Substring Without Repeating Characters/Solution.java5-11

Multi-Language Implementations

Python Implementation

The Python solution uses Counter from collections for frequency tracking:

cnt = Counter()
ans = l = 0
for r, c in enumerate(s):
    cnt[c] += 1
    while cnt[c] > 1:
        cnt[s[l]] -= 1
        l += 1
    ans = max(ans, r - l + 1)

Key Functions:

• enumerate(s): Returns (index, character) pairs for iteration
• Counter(): Hash map for character frequencies
• max(ans, r - l + 1): Updates maximum window size

Sources: solution/0000-0099/0003.Longest Substring Without Repeating Characters/Solution.py1-11

Java Implementation

The Java solution uses a fixed-size array for ASCII characters:

int[] cnt = new int[128];
for (int l = 0, r = 0; r < n; ++r) {
    char c = s.charAt(r);
    ++cnt[c];
    while (cnt[c] > 1) {
        --cnt[s.charAt(l++)];
    }
    ans = Math.max(ans, r - l + 1);
}

Key Functions:

• s.charAt(r): Accesses character at index r
• cnt[c]: Direct array indexing using character as index
• l++: Post-increment within array access s.charAt(l++)

Sources: solution/0000-0099/0003.Longest Substring Without Repeating Characters/Solution.java1-15

C++ Implementation

The C++ solution uses stack-allocated array for efficiency:

int cnt[128]{};
for (int l = 0, r = 0; r < n; ++r) {
    ++cnt[s[r]];
    while (cnt[s[r]] > 1) {
        --cnt[s[l++]];
    }
    ans = max(ans, r - l + 1);
}

Key Features:

• int cnt[128]{}: Zero-initialized array on stack
• s[r]: Direct string indexing (C++ strings support operator[])
• max(ans, r - l + 1): STL algorithm for maximum

Sources: solution/0000-0099/0003.Longest Substring Without Repeating Characters/Solution.cpp1-15

TypeScript Implementation

The TypeScript solution uses Map for type-safe frequency tracking:

const cnt = new Map<string, number>();
for (let l = 0, r = 0; r < n; ++r) {
    cnt.set(s[r], (cnt.get(s[r]) || 0) + 1);
    while (cnt.get(s[r])! > 1) {
        cnt.set(s[l], cnt.get(s[l])! - 1);
        ++l;
    }
    ans = Math.max(ans, r - l + 1);
}

Key Functions:

• Map<string, number>: Type-safe hash map
• cnt.get(s[r]) || 0: Returns 0 if key doesn't exist
• cnt.get(s[r])!: Non-null assertion operator

Sources: solution/0000-0099/0003.Longest Substring Without Repeating Characters/Solution.ts1-14

Implementation Comparison

Language	Counter Type	Space	Iteration	Notes
Python	Counter()	O(Σ)	enumerate(s)	Dynamic hash map, clean syntax
Java	int[128]	O(1)	for (l=0, r=0; ...)	Fixed array, fastest for ASCII
C++	int cnt[128]{}	O(1)	for (l=0, r=0; ...)	Stack-allocated, zero-initialized
TypeScript	Map<string, number>	O(Σ)	for (let l=0, r=0; ...)	Type-safe, flexible
Go	[128]int{}	O(1)	for r, c := range s	Array literal, range iteration
Rust	[0; 128]	O(1)	enumerate()	Array with explicit size
C#	int[128]	O(1)	for (l=0, r=0; ...)	Similar to Java
PHP	array_fill(0, 128, 0)	O(1)	for ($r=0; ...)	Dynamic array as fixed array

Sources: solution/0000-0099/0003.Longest Substring Without Repeating Characters/Solution.py1-11 solution/0000-0099/0003.Longest Substring Without Repeating Characters/Solution.java1-15 solution/0000-0099/0003.Longest Substring Without Repeating Characters/Solution.cpp1-15 solution/0000-0099/0003.Longest Substring Without Repeating Characters/Solution.ts1-14 solution/0000-0099/0003.Longest Substring Without Repeating Characters/Solution.go1-13

Complexity Analysis

Time Complexity

O(n) where n is the length of the string s.

Analysis:

• The right pointer r iterates through the string exactly once: O(n)
• The left pointer l also moves at most n times across the entire execution
• Each character is visited at most twice (once by r expanding, once by l contracting)
• Inner while loop operations are amortized O(1) per character
• Total operations: O(n + n) = O(n)

Sources: solution/0000-0099/0003.Longest Substring Without Repeating Characters/README.md73 solution/0000-0099/0003.Longest Substring Without Repeating Characters/README_EN.md71

Space Complexity

O(|Σ|) where |Σ| is the size of the character set.

Breakdown:

Implementation	Space	Explanation
Array-based (int[128])	O(1)	Fixed size for ASCII character set
Hash Map-based (Counter, Map)	O(min(n,	Σ
Practical	O(128) = O(1)	For ASCII, this is constant
General	O(	Σ

The algorithm ignores the space used by the answer, following the convention that output space is not counted in space complexity analysis.

Sources: solution/0000-0099/0003.Longest Substring Without Repeating Characters/README.md73 solution/0000-0099/0003.Longest Substring Without Repeating Characters/README_EN.md71

Pattern Variants

The sliding window pattern has several variants depending on the problem requirements:

Problem 0003 Characteristics:

• Type: Variable-size window, maximize window
• Invariant: cnt[s[r]] <= 1 (no duplicate characters)
• Expansion: Always expand by incrementing r
• Contraction: Contract when invariant violated (cnt[s[r]] > 1)
• Answer: Maximum value of r - l + 1 across all valid windows

Sources: solution/0000-0099/0003.Longest Substring Without Repeating Characters/README.md65-71

Code Structure Map

Function Signatures:

Language	Signature
Python	def lengthOfLongestSubstring(self, s: str) -> int:
Java	public int lengthOfLongestSubstring(String s)
C++	int lengthOfLongestSubstring(string s)
TypeScript	function lengthOfLongestSubstring(s: string): number
Go	func lengthOfLongestSubstring(s string) (ans int)
Rust	pub fn length_of_longest_substring(s: String) -> i32

Sources: solution/0000-0099/0003.Longest Substring Without Repeating Characters/Solution.py2 solution/0000-0099/0003.Longest Substring Without Repeating Characters/Solution.java2 solution/0000-0099/0003.Longest Substring Without Repeating Characters/Solution.cpp3 solution/0000-0099/0003.Longest Substring Without Repeating Characters/Solution.ts1 solution/0000-0099/0003.Longest Substring Without Repeating Characters/Solution.go1 solution/0000-0099/0003.Longest Substring Without Repeating Characters/Solution.rs2

Pattern Recognition

When to Use Sliding Window:

The sliding window pattern is applicable when a problem exhibits these characteristics:

Characteristic	Description	Example
Contiguous subsequence	Problem asks about subarrays/substrings	"Find longest substring..."
Optimization goal	Maximize, minimize, or count	"Longest", "shortest", "number of"
Window invariant	A clear condition to maintain	"Without repeating characters"
Linear scan	Can be solved by scanning once	Each element processed in order

Problem 0003 Indicators:

1. ✓ Input is a string (contiguous sequence)
2. ✓ Asks for "longest substring" (optimization)
3. ✓ Has clear constraint: "without repeating characters" (invariant)
4. ✓ Can be solved in single pass with two pointers

Sources: solution/0000-0099/0003.Longest Substring Without Repeating Characters/README.md13-58 solution/0000-0099/0003.Longest Substring Without Repeating Characters/README_EN.md13-55

Related Patterns

The sliding window pattern relates to other algorithmic techniques in the repository:

• Hash Table Pattern: Uses hash tables/arrays for frequency counting (cnt in problem 0003)
• Two Pointers Pattern: Sliding window is a specialized two-pointer technique where pointers move in the same direction
• Dynamic Programming: Some DP problems can be optimized using sliding window to reduce space complexity
• Binary Search Pattern: Can combine with sliding window when searching for optimal window size

Difference from Two Pointers:

• Sliding window maintains a contiguous range [l, r]
• Two pointers may move independently or toward each other (e.g., left and right ends)
• Sliding window typically optimizes within the window, two pointers often compare elements at boundaries

Sources: solution/0000-0099/0003.Longest Substring Without Repeating Characters/README.md5-8