Common String Patterns & Problem-Solving Techniques

When you first learn to traverse a string, you use a single index—moving from left to right (or right to left), examining one character at a time. This is fundamental, but it's also limiting. Many string problems require reasoning about two positions simultaneously: comparing characters at opposite ends, tracking a range of interest, or processing pairs of elements.

The two-pointer technique addresses these problems by maintaining two position markers that move through the string according to problem-specific rules. This simple idea—two indices instead of one—unlocks efficient solutions to a surprisingly large class of problems.

This page builds your intuition for two-pointer thinking on strings. We won't implement specific algorithms here; instead, we'll develop the mental model that lets you recognize when two pointers apply and how to reason about their movement.

At its heart, the two-pointer technique exploits a simple observation:

If examining all pairs of positions naively would take O(n²) time, then perhaps we can use problem structure to avoid examining most pairs.

Consider a string of length n. There are n × n = n² pairs of positions (i, j). A naive approach examining all pairs is quadratic. But often, the problem has structure that lets us:

1. Start with a carefully chosen initial pair
2. Move one or both pointers based on what we observe
3. Visit only O(n) pairs total while still finding the answer

This reduction from O(n²) to O(n) is the power of two-pointer techniques.

Why Two Pointers, Not Three or Four?

Two pointers are sufficient for problems involving:

• Pairs of characters (palindrome checking, two-sum-like queries)
• Ranges defined by start and end (substrings, windows)
• Relative positions (leader/follower, fast/slow)

More complex problems sometimes use three pointers (Dutch national flag) or more, but two covers the vast majority of linear-structure problems.

Not Magic—Problem Structure Required

Two-pointer techniques aren't universally applicable. They work when the problem has monotonicity or ordering that lets us make progress with each move. If no such structure exists, two pointers won't help—you genuinely need to check all pairs.

Two-pointer techniques on strings fall into two main patterns, each with a distinct mental model.

Pattern 1: Opposite-Direction (Converging) Pointers

Two pointers start at opposite ends and move toward each other.

Initially:   L →                        ← R
            [ a ] [ b ] [ c ] [ d ] [ e ]
              0     1     2     3     4

After moves: ... → L         R ← ...
            [ a ] [ b ] [ c ] [ d ] [ e ]
              0     1     2     3     4

Use when: You need to compare/process from both ends, or when the answer involves opposite ends meeting in the middle.

Examples:

• Palindrome checking (compare first and last, move inward)
• Reversing a string in place
• Two-sum in sorted array (adjust sum by moving appropriate pointer)
• Container with most water (area determined by two sides)

Pattern 2: Same-Direction (Co-Moving) Pointers

Both pointers start at or near the same position and move in the same direction, though at different speeds or conditions.

Initially:   S, F →
            [ a ] [ b ] [ c ] [ d ] [ e ]
              0     1     2     3     4

After moves: S →          F →
            [ a ] [ b ] [ c ] [ d ] [ e ]
              0     1     2     3     4

Use when: You need to track a range (window) or distinguish between two regions of the array.

Examples:

• Slow/Fast pointers for cycle detection (not typically on strings, but same idea)
• Maintaining a window (covered in next page on sliding window)
• Removing duplicates in place
• Partitioning elements

Let's develop deep intuition for converging pointers through the classic application: palindrome checking.

The Problem: Determine if a string reads the same forwards and backwards.

The Naive Approach:

• Create the reversed string
• Compare to original
• Time: O(n), Space: O(n)

The Two-Pointer Approach:

• Compare first character with last, second with second-to-last, etc.
• If all pairs match, it's a palindrome
• Time: O(n), Space: O(1)

Why This Works:

A palindrome has the property: S[i] = S[n-1-i] for all valid i. The two pointers check exactly these symmetric pairs. Once left crosses right, we've verified all necessary pairs.

The Insight About Pairs Examined:

We examine at most n/2 pairs (each iteration compares one pair and moves both pointers). This is O(n) time, but we never explicitly enumerate all n² pairs—the structure of the problem tells us exactly which pairs matter.

Variations:

• Skip non-alphanumeric characters (for "A man, a plan, a canal: Panama")
• Case-insensitive comparison
• Allow one mismatch (Valid Palindrome II problem)

Co-moving pointers (also called slow/fast or read/write pointers) are essential for in-place string modifications and range tracking.

Canonical Example: Removing Duplicates

Given a sorted string, remove duplicate characters in place.

The Mental Model:

• Slow pointer (write): Marks the position where next unique character should be written
• Fast pointer (read): Scans ahead to find the next unique character

The intuition: slow pointer represents "the cleaned portion," fast pointer represents "exploration into unseen territory."

Key Observations:

1. Write pointer is always ≤ read pointer: We can overwrite positions we've already read.

2. No extra space needed: We're modifying in place, achieving O(1) space.

3. Single pass: Both pointers move left to right, total O(n) time.

4. Invariant maintained: Everything before write pointer is the final result so far.

Why "Fast" and "Slow"?

In this example, both pointers move, but fast moves every iteration while slow moves only sometimes. Over time, fast "outruns" slow, creating a gap. This gap represents duplicates that were skipped.

The key to two-pointer success is knowing when and how to move each pointer. Here are the main strategies:

Strategy 1: Alternating Movement

Used in converging pointer problems where you always move both pointers symmetrically.

WHILE left < right:
    Process S[left] and S[right]
    left += 1
    right -= 1

When to use: Palindrome checking, string reversal—problems where you process symmetric pairs.

Strategy 2: Conditional Movement Based on Comparison

Used when the decision to move depends on evaluating the current state.

WHILE left < right:
    IF condition_favors_left:
        left += 1
    ELSE:
        right -= 1

When to use: Two-sum in sorted array (move left if sum too small, right if too large), container with most water.

Strategy 3: Fast Always Moves, Slow Conditionally

Used in filtering/partition problems.

FOR fast = 0 TO n-1:
    IF should_keep(S[fast]):
        S[slow] = S[fast]
        slow += 1

When to use: Removing elements, deduplication, filtering characters.

Strategy 4: Expand/Contract Window

Used in sliding window problems (covered in next page). Right pointer expands the window, left pointer contracts it.

FOR right = 0 TO n-1:
    // Expand window by including S[right]
    WHILE window_invalid:
        // Contract by excluding S[left]
        left += 1
    // Process valid window

Developing the instinct to recognize two-pointer problems is as important as knowing how to implement them. Here are the signals to watch for:

Signal 1: Symmetric or End-to-End Structure

Keywords: "palindrome," "symmetric," "reverse," "from both ends"

Why two pointers: Symmetric structures naturally pair first with last, second with second-to-last.

Signal 2: Sorted/Ordered Data

Keywords: "sorted array," "sorted string," "in order"

Why two pointers: Ordered data has monotonicity. Moving a pointer in one direction consistently increases or decreases some property, enabling binary-search-like elimination.

Signal 3: In-Place Modification with O(1) Space Constraint

Keywords: "in place," "constant extra space," "do not use additional array"

Why two pointers: In-place modification often requires distinguishing between "processed" and "unprocessed" regions—perfect for slow/fast pointers.

Signal 4: Finding Pairs or Subranges

Keywords: "find a pair," "find two elements," "subarray summing to," "contiguous substring"

Why two pointers: Pairs and ranges are defined by two positions. Two pointers let you explore the space of pairs/ranges efficiently.

Signal 5: Comparison/Merging from Two Sources

Keywords: "merge two sorted," "compare two strings from ends"

Why two pointers: When processing two sequences together, one pointer per sequence is natural.

When applying two-pointer techniques to strings (versus arrays of numbers), some string-specific concerns arise:

Consideration 1: Mutability

In many languages (Java, Python, JavaScript), strings are immutable. You cannot change a character in place. This affects in-place two-pointer algorithms:

Workarounds:

• Convert string to character array, manipulate, convert back
• Build output in a separate structure (loses O(1) space advantage)
• Use language-specific mutable string types (e.g., StringBuffer in Java)

In languages with mutable strings (C, C++), direct in-place modification is possible.

Consideration 2: Character Filtering

Many problems require ignoring certain characters (non-alphanumeric, spaces, punctuation). The two-pointer logic must skip these:

// Palindrome check ignoring non-letters
WHILE left < right:
    WHILE left < right AND NOT isLetter(S[left]):
        left += 1
    WHILE left < right AND NOT isLetter(S[right]):
        right -= 1
    IF toLower(S[left]) ≠ toLower(S[right]):
        RETURN false
    left += 1
    right -= 1
RETURN true

Consideration 3: Case Sensitivity

Comparing characters often requires case-insensitive matching. Always normalize (toLower or toUpper) before comparing.

Consideration 4: Unicode and Multi-Byte Characters

In Unicode strings, what appears as one character might be multiple code points (accent marks, emoji with modifiers). Indexing by code unit can produce incorrect results.

For interview problems: Usually, you can assume ASCII or simple Unicode. But in production code, be aware of grapheme clusters.

Consideration 5: String Length Checks

Always handle edge cases:

• Empty string (length 0): Usually trivially valid for palindrome, nothing to reverse, etc.
• Single character: Also trivially valid for symmetric properties

These checks should happen before pointer initialization to avoid out-of-bounds access.

Two-pointer algorithms are prized for their efficiency. Let's analyze why:

Time Complexity: O(n)

In both converging and co-moving patterns, we can bound the total pointer movements:

Converging:

• Left pointer moves right at most n/2 times
• Right pointer moves left at most n/2 times
• Total: O(n)

Co-moving:

• Fast pointer moves right exactly n times (once per element)
• Slow pointer moves right at most n times (it never goes backward)
• Total: O(n)

Key Insight: Even though we have two pointers, they collectively cover O(n) positions, not O(n) each independently. The linear time bound comes from the fact that progress is always made.

Space Complexity: O(1)

Two-pointer algorithms typically use only a constant amount of extra space (the pointer variables themselves). This is their primary advantage over alternatives like:

• Reversing by creating a new string: O(n) space
• Hashing all pairs: O(n²) space
• Recursion with call stack: O(n) space

Comparison with Alternatives:

This page has focused on building intuition. Here's a framework for translating that intuition into working code:

Step 1: Identify the Pattern

Ask yourself:

• Am I comparing ends of a structure? → Converging
• Am I filtering or partitioning in place? → Co-moving
• Am I tracking a range with variable boundaries? → Will become sliding window (next page)

Step 2: Define Pointer Roles

Give each pointer a clear purpose:

• "Left marks unverified region, right marks end"
• "Slow marks write position, fast marks read position"
• "Left is the window start, right is the window end"

Clear roles prevent confusion about when each should move.

Step 3: Establish Loop Invariants

What is true at the start of each loop iteration?

• "All positions before left have been processed"
• "The substring S[left:right+1] satisfies property P"

Invariants guide your movement decisions and help prove correctness.

Step 4: Define Movement Conditions

For each pointer, specify exactly when it moves:

• "Left moves when we find a matching pair"
• "Right moves when the condition is violated"
• "Both move when we've processed the current pair"

Step 5: Handle Edge Cases

Before the main loop:

• Empty input
• Single element
• All elements filtered out

During the loop:

• Pointers meeting/crossing
• Out-of-bounds access

The two-pointer technique is one of the most versatile tools for string (and array) problems. We've built intuition for when and how it applies: