String Algorithms

After this lesson, you will be able to: Apply the sliding window and two-pointer patterns to string and array problems, and understand substring search with KMP or Rabin-Karp.

String problems are everywhere in interviews, and a few patterns solve most of them. Sliding window and two pointers turn many O(n squared) brute-force solutions into O(n). Substring search algorithms show how to find a pattern in text efficiently.

Prerequisites:Graph Algorithms

The two-pointer pattern

Two pointers walk through a sequence from different positions, often from both ends toward the middle, or one fast and one slow. It replaces a nested loop with a single pass. For a sorted array, finding a pair that sums to a target is O(n) with two pointers instead of O(n squared) with nested loops: move the left pointer right to increase the sum, the right pointer left to decrease it. The same idea reverses strings, removes duplicates in place, and merges sorted arrays.

Two pointers: pair sum in a sorted array

O(n) time, O(1) space.

python

def two_sum_sorted(arr, target):
    lo, hi = 0, len(arr) - 1
    while lo < hi:
        s = arr[lo] + arr[hi]
        if s == target:
            return (lo, hi)
        elif s < target:
            lo += 1            # need a bigger sum
        else:
            hi -= 1            # need a smaller sum
    return None
# two_sum_sorted([1,2,4,7,11], 13) -> (2, 4)  (4 + 11)

The sliding window pattern

Grow and shrink a window over the input. Great for substring and subarray problems.

python

def longest_unique_substring(s):
    # Longest substring with no repeated characters.
    seen = {}            # char -> last index
    start = best = 0
    for end, ch in enumerate(s):
        if ch in seen and seen[ch] >= start:
            start = seen[ch] + 1   # shrink window past the repeat
        seen[ch] = end
        best = max(best, end - start + 1)
    return best
# longest_unique_substring("abcabcbb") -> 3 ("abc")
# One pass, O(n). The window [start, end] never moves backward.

Substring search: naive vs KMP vs Rabin-Karp

Finding a pattern of length m inside text of length n: the naive approach checks every position and is O(n times m). KMP (Knuth-Morris-Pratt) precomputes a table of how far to skip on a mismatch, achieving O(n + m) by never re-examining characters. Rabin-Karp uses a rolling hash to compare the pattern's hash to each window's hash in O(n + m) average time, which generalizes nicely to searching for multiple patterns. You rarely implement these from scratch (your language's find/indexOf is optimized), but interviewers ask about the ideas.

Common mistakes only experienced devs catch

Using two pointers on an unsorted array when the technique needs sorted input. Moving the window start backward (it should only ever advance in a standard sliding window). Off-by-one errors in the window size (end - start + 1). Reimplementing substring search when the built-in is faster and correct. Building new strings inside a loop (O(n squared)); use indices and a result list. Forgetting that the fast/slow pointer trick needs the right step sizes to detect cycles.

←Graph Algorithms

Back to Algorithms

Backtracking→