# Common String Manipulation Patterns and Techniques for LeetCode Solutions

> Unlock LeetCode string solutions with six key patterns like two-pointer sliding windows, prefix sums, tries, rolling hash, DP, and greedy frequency analysis. Solve problems faster.

- Repository: [lucifer/leetcode](https://github.com/azl397985856/leetcode)
- Tags: tutorial
- Published: 2026-03-06

---

**Mastering six core patterns—two-pointer sliding windows, prefix sums, tries, rolling hash, dynamic programming, and greedy frequency analysis—solves the majority of LeetCode string problems in linear or polynomial time.**

The `azl397985856/leetcode` repository catalogs reusable algorithmic templates for solving string manipulation problems efficiently. Understanding these common string manipulation patterns and techniques allows you to recognize problem structures instantly and implement optimized solutions without reinventing fundamental logic.

## Two-Pointer and Sliding Window Techniques

The two-pointer approach is the dominant pattern for substring and subarray problems. As documented in [`thinkings/slide-window.md`](https://github.com/azl397985856/leetcode/blob/main/thinkings/slide-window.md) and [`thinkings/string-problems.md`](https://github.com/azl397985856/leetcode/blob/main/thinkings/string-problems.md), this technique maintains a contiguous window of characters using left and right indices.

### Fixed-Size Window Pattern

Use this when the problem asks for the minimum or maximum property of every substring of length `k`. The core invariant maintains `r - l + 1 == k` by moving both pointers simultaneously after the initial window is formed.

```python
def max_sum_subarray(nums, k):
    window_sum = sum(nums[:k])
    max_sum = window_sum
    for right in range(k, len(nums)):
        window_sum += nums[right] - nums[right - k]
        max_sum = max(max_sum, window_sum)
    return max_sum

```

### Variable-Size Window Pattern

This pattern applies to problems like "Longest Substring Without Repeating Characters" (see [`problems/3.longestSubstringWithoutRepeatingCharacters.md`](https://github.com/azl397985856/leetcode/blob/main/problems/3.longestSubstringWithoutRepeatingCharacters.md)). Expand the right pointer while the constraint holds, then shrink the left pointer until the window becomes valid again.

```python
def length_of_longest_substring(s: str) -> int:
    seen = {}
    left = 0
    best = 0
    for right, ch in enumerate(s):
        if ch in seen and seen[ch] >= left:
            left = seen[ch] + 1
        seen[ch] = right
        best = max(best, right - left + 1)
    return best

```

### Two-Pointer Palindrome Validation

For checking palindromes or pair sums on sorted strings, initialize pointers at both ends and move them toward the center. This technique appears in [`problems/125.valid-palindrome.md`](https://github.com/azl397985856/leetcode/blob/main/problems/125.valid-palindrome.md).

```python
def is_palindrome(s: str) -> bool:
    left, right = 0, len(s) - 1
    while left < right:
        while left < right and not s[left].isalnum():
            left += 1
        while left < right and not s[right].isalnum():
            right -= 1
        if s[left].lower() != s[right].lower():
            return False
        left += 1
        right -= 1
    return True

```

## Prefix Sum and Difference Array Techniques

The prefix sum pattern, detailed in [`thinkings/prefix.md`](https://github.com/azl397985856/leetcode/blob/main/thinkings/prefix.md), transforms range sum queries from O(N) to O(1) after O(N) preprocessing.

### Running Sum for Range Queries

Build an array where each element at index `i` contains the sum of all elements up to `i`. The sum of any subarray `l` to `r` becomes `prefix[r] - prefix[l-1]`.

```python
class NumArray:
    def __init__(self, nums):
        self.prefix = [0]
        for x in nums:
            self.prefix.append(self.prefix[-1] + x)

    def sumRange(self, left, right):
        return self.prefix[right + 1] - self.prefix[left]

```

### Difference Array for Range Updates

When you need to add a value to every element in a range `[l, r]`, use a difference array. Mark `+k` at index `l` and `-k` at index `r+1`, then compute the prefix sum to get the final array.

```python
def get_modified_array(length, updates):
    diff = [0] * (length + 1)
    for l, r, val in updates:
        diff[l] += val
        diff[r + 1] -= val
    
    result = []
    current = 0
    for i in range(length):
        current += diff[i]
        result.append(current)
    return result

```

## Trie Data Structure for String Storage

The trie pattern, documented in [`thinkings/trie.md`](https://github.com/azl397985856/leetcode/blob/main/thinkings/trie.md), provides O(L) insertion and lookup where L is the word length. This structure excels at prefix-based queries and autocomplete scenarios.

```python
class TrieNode:
    def __init__(self):
        self.children = {}
        self.is_word = False

class Trie:
    def __init__(self):
        self.root = TrieNode()

    def insert(self, word: str) -> None:
        node = self.root
        for ch in word:
            node = node.children.setdefault(ch, TrieNode())
        node.is_word = True

    def search(self, word: str) -> bool:
        node = self.root
        for ch in word:
            if ch not in node.children:
                return False
            node = node.children[ch]
        return node.is_word

    def startsWith(self, prefix: str) -> bool:
        node = self.root
        for ch in prefix:
            if ch not in node.children:
                return False
            node = node.children[ch]
        return True

```

## Rolling Hash and Rabin-Karp Algorithm

For substring search and anagram detection, the rolling hash technique discussed in [`thinkings/string-problems.md`](https://github.com/azl397985856/leetcode/blob/main/thinkings/string-problems.md) provides O(N) substring comparison by maintaining a running hash value.

```python
def find_anagrams(s: str, p: str):
    from collections import Counter
    need = Counter(p)
    window = Counter()
    result = []
    left = 0
    
    for right, ch in enumerate(s):
        window[ch] += 1
        
        if right - left + 1 > len(p):
            window[s[left]] -= 1
            if window[s[left]] == 0:
                del window[s[left]]
            left += 1
            
        if window == need:
            result.append(left)
            
    return result

```

## Dynamic Programming on Strings

String DP problems, covered in [`thinkings/dynamic-programming.md`](https://github.com/azl397985856/leetcode/blob/main/thinkings/dynamic-programming.md) and [`thinkings/string-problems.md`](https://github.com/azl397985856/leetcode/blob/main/thinkings/string-problems.md), typically involve computing optimal substructure on substrings or subsequences.

### Longest Palindromic Subsequence

```python
def longest_palindrome_subseq(s: str) -> int:
    n = len(s)
    dp = [[0] * n for _ in range(n)]
    
    for i in range(n):
        dp[i][i] = 1
        
    for length in range(2, n + 1):
        for i in range(n - length + 1):
            j = i + length - 1
            if s[i] == s[j]:
                dp[i][j] = dp[i + 1][j - 1] + 2
            else:
                dp[i][j] = max(dp[i + 1][j], dp[i][j - 1])
                
    return dp[0][n - 1]

```

### Edit Distance

```python
def min_distance(word1: str, word2: str) -> int:
    m, n = len(word1), len(word2)
    dp = [[0] * (n + 1) for _ in range(m + 1)]
    
    for i in range(m + 1):
        dp[i][0] = i
    for j in range(n + 1):
        dp[0][j] = j
        
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if word1[i-1] == word2[j-1]:
                dp[i][j] = dp[i-1][j-1]
            else:
                dp[i][j] = 1 + min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1])
                
    return dp[m][n]

```

## Greedy Techniques Using Character Frequencies

For problems requiring optimal substrings with constraints on character counts, greedy approaches using hashmaps often yield O(N) solutions, as detailed in [`thinkings/greedy.md`](https://github.com/azl397985856/leetcode/blob/main/thinkings/greedy.md) and [`thinkings/string-problems.md`](https://github.com/azl397985856/leetcode/blob/main/thinkings/string-problems.md).

### Minimum Window Substring

```python
from collections import Counter, defaultdict

def min_window(s: str, t: str) -> str:
    need = Counter(t)
    missing = len(t)
    left = start = end = 0
    
    for right, ch in enumerate(s, 1):
        if need[ch] > 0:
            missing -= 1
        need[ch] -= 1
        
        if missing == 0:
            while s[left] not in need or need[s[left]] < 0:
                need[s[left]] += 1
                left += 1
            if end == 0 or right - left < end - start:
                start, end = left, right
            need[s[left]] += 1
            missing += 1
            left += 1
            
    return s[start:end]

```

## Summary

- **Two-pointer sliding window** techniques handle substring problems in linear time by maintaining valid window invariants, as implemented in [`thinkings/slide-window.md`](https://github.com/azl397985856/leetcode/blob/main/thinkings/slide-window.md).
- **Prefix sums and difference arrays** transform range queries and updates from O(N) to O(1) after O(N) preprocessing, detailed in [`thinkings/prefix.md`](https://github.com/azl397985856/leetcode/blob/main/thinkings/prefix.md).
- **Trie data structures** provide O(L) insertion and lookup for prefix-based string storage, covered in [`thinkings/trie.md`](https://github.com/azl397985856/leetcode/blob/main/thinkings/trie.md).
- **Rolling hash (Rabin-Karp)** enables constant-time substring comparison and anagram detection via sliding hash windows.
- **Dynamic programming** solves optimal substructure problems on strings using recurrences for palindromes and edit distance, documented in [`thinkings/dynamic-programming.md`](https://github.com/azl397985856/leetcode/blob/main/thinkings/dynamic-programming.md).
- **Greedy frequency analysis** optimizes constrained substring problems by shrinking valid windows while tracking character counts.

## Frequently Asked Questions

### What is the most efficient pattern for finding substrings in linear time?

The **sliding window** approach combined with **rolling hash** (Rabin-Karp) provides O(N) substring search. By maintaining a running hash value as the window slides, you avoid recomputing hash values from scratch, allowing constant-time updates per character shift.

### When should I use a Trie instead of a hash map for string problems?

Use a **Trie** when you need to store strings for **prefix-based queries** or when memory efficiency across shared prefixes matters. While hash maps provide O(1) exact lookups, Tries excel at operations like `startsWith`, autocomplete suggestions, and counting words with common prefixes in O(L) time where L is the word length.

### How do I choose between sliding window and dynamic programming for string optimization?

Choose **sliding window** when the problem asks for a **contiguous substring** with constraints that can be satisfied by expanding and shrinking a single window (e.g., "longest substring without repeating characters"). Choose **dynamic programming** when the problem involves **non-contiguous subsequences**, optimal edit operations, or palindromic properties where subproblems overlap (e.g., "longest palindromic subsequence" or "edit distance").

### What is the difference between prefix sum and difference array techniques?

**Prefix sums** preprocess an array to answer **range sum queries** in O(1) time by storing cumulative sums, allowing you to calculate `sum(l..r)` as `prefix[r] - prefix[l-1]`. **Difference arrays** work in reverse: they allow **range updates** (adding a value to all elements in a range) to be performed in O(1) by marking start and end+1 positions, then applying a final prefix sum to reconstruct the modified array.