Sliding Window: Substrings vs Subarrays — What’s the Difference?

In the world of LeetCode, "Sliding Window" is often thrown around as a catch-all term. But applying it to a String (Substring) is subtly different from applying it to an Array (Subarray).

While the core mechanics (expanding right, shrinking left) remain the same, the state you maintain and the edge cases you face differ significantly.

In this guide, we will clarify the definitions, compare the implementation details, and provide a decision table to help you choose the right approach.

TL;DR — The Cheat Sheet

• String (Substring):
  • Goal: Find pattern / unique chars.
  • Tool: Hash Map / Frequency Array (size 128).
  • Watch out for: Anagrams vs Palindromes.
• Array (Subarray):
  • Goal: Sum / Product / Min / Max.
  • Tool: Integer variable (sum) or Monotonic Queue.
  • Watch out for: Negative numbers (breaks monotonicity).

Definitions

Substring (String Context)

A substring is a contiguous sequence of characters within a string.

• Example: In "abcde", "bcd" is a substring. "ace" is a subsequence (not contiguous).
• Key Characteristic: Elements are characters. The "alphabet" size is usually small (26 lowercase letters or 128/256 ASCII).

Subarray (Array Context)

A subarray is a contiguous sequence of elements within an array.

• Example: In [1, 2, 3, 4], [2, 3] is a subarray.
• Key Characteristic: Elements are usually numbers. The range of values can be infinite (negative, positive, large integers).

How sliding window applies differently

Fixed length in string (e.g., Permutations)

String problems often ask for fixed-length windows, such as "Find all anagrams of 'abc' in s".

• State: You typically use a frequency array of size 26 (e.g., int[26]) or a Hash Map.
• Comparison: You compare two frequency arrays. This is $O(1)$ (constant 26 checks) rather than $O(N)$.

Variable length in array (e.g., Sum ≤ K)

Array problems often involve numerical constraints, like "Sum of subarray $\le K$".

• State: You maintain a running currentSum.
• Shrinking: You shrink based on numerical value (subtracting nums[left]), not character counts.

Example scenarios

String Scenarios

1. Longest Substring Without Repeating Characters:
   • State: Set<char> or Map<char, index>.
   • Condition: Duplicate character found.
2. Minimum Window Substring (containing all chars of T):
   • State: Map<char, count> (needed vs have).
   • Condition: "Have" counts match "Needed" counts.

Array Scenarios

1. Max Consecutive Ones (with K flips):
   • State: Count of zeros in window.
   • Condition: Zero count $>K$.
2. Subarray Product Less Than K:
   • State: Running product.
   • Condition: Product $\ge K$.

Pitfalls when confused

Character frequency vs Numeric sum

A common mistake is trying to sum up characters (using ASCII values) to check for anagrams.

• Why it fails: "ac" (1 + 3 = 4) has the same sum as "bb" (2 + 2 = 4). Sums are not unique fingerprints for strings.
• Fix: Always use a Frequency Map or Array for strings.

When to treat as substring vs subarray

Sometimes an array problem is just a string problem in disguise.

• Example: "Longest subarray with equal number of 0s and 1s."
• Strategy: This is actually a Prefix Sum problem (transform 0 to -1), not a standard sliding window.

Code Comparison: String vs Array State

Notice how the "State" management differs in code.

String State (Map/Set)

let charCount = new Map<string, number>();
// Expand
charCount.set(s[right], (charCount.get(s[right]) || 0) + 1);
// Shrink
if (charCount.get(s[left]) === 1) charCount.delete(s[left]);
else charCount.set(s[left], charCount.get(s[left])! - 1);

Array State (Sum)

let currentSum = 0;
// Expand
currentSum += nums[right];
// Shrink
currentSum -= nums[left];

Decision table: “Is it substring or subarray?”

FAQ

Q: Are all string problems substring problems?
A: No! "Subsequence" means characters don't need to be adjacent (e.g., "ace" is a subsequence of "abcde"). Sliding Window cannot solve subsequence problems; you usually need Dynamic Programming or Two Pointers.

Q: Can I use Sliding Window on a sorted array?
A: You can, but if you are looking for a pair of numbers (e.g., Two Sum), the Two Pointers technique (one at start, one at end) is more standard. Sliding Window is better for ranges (subarrays).

Summary

• Substrings are about patterns, frequencies, and uniqueness. Your tools are Hash Maps and Sets.
• Subarrays are about mathematical aggregation (sums, products). Your tools are accumulators.

Next Step:
Now that you know the difference, learn how to debug your implementation in Why Your Sliding Window Shrinks Wrong.