Three patterns for substring and subarray questions

Coding-interview substring and subarray problems often reduce to one of three patterns.

1. Sliding window (two pointers)

Use a sliding window when the constraint changes monotonically as you expand or shrink the window.

  • Use it for: substrings with “at most K distinct characters,” all unique characters, or subarrays with sum constraints when all numbers are nonnegative.
  • Core idea: Expand right to include a new element. If the window becomes invalid, move left until it is valid again.
  • Counting pattern: When removing items from the left preserves validity, every start index from left through right forms a valid window ending at right. Add right - left + 1.
  • Complexity: O(N) time, usually O(1) or O(K) space.
  • Classic example: Number of Substrings With At Most K Distinct Characters. Track character frequencies, shrink until the window has at most K distinct characters, then add right - left + 1.

For “exactly K distinct characters,” use:

Exactly(K) = AtMost(K) - AtMost(K - 1)

2. Prefix sums + hash map

Use prefix sums for subarray problems with exact algebraic conditions, especially when negative values make a sum-based sliding window unreliable.

  • Use it for: subarrays with sum K, equal numbers of 0s and 1s, or sums divisible by K.
  • Core idea: The sum from i through j is prefix[j] - prefix[i - 1]. For a target sum T, find earlier prefix sums equal to currentSum - T.
  • Execution: Maintain a running sum and a map from prefix sum to frequency. At each index, add the frequency of currentSum - target to the answer, then record currentSum.
  • Complexity: O(N) time, O(N) space.
  • Classic example: Subarray Sum Equals K.

3. Combinatorics

Use counting formulas when valid substrings come from independent runs or when every substring is valid.

  • Use it for: substrings made entirely of the same character, or problems where all substrings qualify.
  • Core idea: A string or run of length L contains L(L + 1) / 2 non-empty substrings.
  • Execution: Find each contiguous run of equal characters. For a run of length L, add L(L + 1) / 2.
  • Complexity: O(N) time, O(1) space.
  • Classic example: Number of Substrings Containing Only 1s.

Quick diagnostic checklist

When you see a substring or subarray counting problem, ask:

  1. Is it a subarray problem with an exact algebraic condition, such as sum K, equal 0s and 1s, or divisibility?
    → Prefix sums + hash map.
  2. Does the constraint support a monotonic window, such as “at most K distinct characters” or a nonnegative sum bound?
    → Sliding window.
  3. Does the answer reduce to counting runs or all possible substrings?
    → Combinatorics.