Common String Manipulation Patterns and Techniques for LeetCode Solutions

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 and 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.

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). Expand the right pointer while the constraint holds, then shrink the left pointer until the window becomes valid again.

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.

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, 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].

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.

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, provides O(L) insertion and lookup where L is the word length. This structure excels at prefix-based queries and autocomplete scenarios.

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 provides O(N) substring comparison by maintaining a running hash value.

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 and thinkings/string-problems.md, typically involve computing optimal substructure on substrings or subsequences.

Longest Palindromic Subsequence

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

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 and thinkings/string-problems.md.

Minimum Window Substring

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.
• 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.
• Trie data structures provide O(L) insertion and lookup for prefix-based string storage, covered in 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.
• 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.

{
  "mcpServers": {
    "instagit": {
      "command": "npx",
      "args": ["-y", "instagit@latest"]
    }
  }
}