ReviseAlgo Logo

Strings

String Two-Pointer & Sliding Window

Master string pattern optimization: palindrome checks, expanding around center, fixed and variable sliding windows, and minimum window substrings.

Last Updated: August 2, 2026 • 25 min read

1. Introduction

What is String Two-Pointer & Sliding Window?

These two algorithms adapt linear index traversal to string problems:
  • Two Pointers: Moving pointers inward from string edges (palindrome verification) or expanding outward from a center character (longest palindromic substring).
  • Sliding Window: Expanding a right index to include characters and shrinking a left index when constraints are violated (finding anagrams, minimum window substrings, or distinct character sub-sequences).

    • Why is it Important?

    Brute-force solutions that generate all O(N²) substrings and check each in O(N) take O(N³) total time. Two Pointers and Sliding Window solve these problems in O(N) linear time and O(1) space.

    Where is it Used?

  • DNA Sequence Alignment: Scanning long genomic sequences for matching gene motifs or repeat patterns.
  • Network Traffic Monitoring: Checking packet payloads for sliding window keyword matches.

    • 2. Mental Model

    Imagine a Flexible Telescope Lens scanning a line of text.

  • For Palindromes: Two inspectors start at opposite ends walking towards the middle. If their characters ever differ, it's not a palindrome!
  • For Substrings: The right lens border expands to take in more characters. If a duplicate or invalid character enters, the left lens border contracts until the window becomes valid again.

    • 3. Concept: Key Algorithmic Patterns

    1. Two Pointers: Valid Palindrome (Converging Pointers)

    2. Two Pointers: Expand Around Center (Longest Palindromic Substring)

    3. Sliding Window: Find All Anagrams in a String

    4. Visuals

    Sliding Window Frequency Comparison

    5. Real-World Examples

  • Plagiarism Detection: Scanning student essays using sliding window N-gram frequency maps to detect copied text blocks.
  • Genome Pattern Matching: Identifying palindromic DNA restriction sites (e.g., GAATTC) where restriction enzymes cut DNA strands.

    • 6. Interview Perspective

    How Interviewers Ask This Topic

    Watch for classic prompts: "Find the longest substring without repeating characters", "Find the smallest substring containing all characters of pattern T", or "Find all anagram start indices".

    Common Mistakes

    Warning: 1. Forget to Handle Even-Length Palindromes: Expanding around a single center (i, i) only finds odd-length palindromes (like "aba"). You must also expand around dual centers (i, i+1) for even-length palindromes (like "abba").
    > 2. Comparing Full Hash Maps Each Step: Comparing two full HashMaps in a variable sliding window takes O(|\Sigma|) time per step. Track a single matched_count integer to keep step updates strictly O(1).

    7. Summary

  • Converging Pointers: Use for palindrome verification (L=0, R=N-1).
  • Expand Around Center: Check all 2N - 1 centers for palindromic substrings in O(N²) time and O(1) space.
  • Fixed Window: Slide window of length |P| over string S comparing character count arrays in O(N) time.

    • 8. Quiz

    Question 1: How many potential palindrome centers exist in a string of length N? Answer: 2N - 1 centers (N single-character centers for odd palindromes + N - 1 adjacent-character centers for even palindromes).
    Question 2: What is the time complexity of finding all anagram occurrences of pattern P in string S? Answer: O(|S|) linear time using a fixed sliding window of size |P| with frequency array comparison.
    Question 3: How does the Minimum Window Substring algorithm shrink its window? Answer: Once the window contains all required characters, advance left rightward, removing s[left] from the window state until the window becomes invalid, recording the minimum valid length at each step.
    Question 4: What is the space complexity of Expand Around Center for Longest Palindromic Substring? Answer: O(1) auxiliary space (storing only index bounds), compared to Dynamic Programming which takes O(N²) space.
    Question 5: Why is checking if a string is a palindrome O(N) time? Answer: Because two pointers move inward from opposite ends, inspecting at most N / 2 pairs of characters before meeting in the middle.