Algorithm Templates: String Processing

Welcome to the String Processing template collection! These are ready-to-use C++ snippets for the core string patterns: sliding window, two pointers, string matching, manipulation, and parsing. If you already know the array templates, you’re most of the way there — strings use the same ideas with character-level twists. See also Arrays & Strings for KMP and rolling hash.

String problems are array problems in disguise. Most string patterns — sliding window, two pointers, prefix computation — work identically to their array counterparts. The main difference is that you operate on characters and often track frequencies with a hash map or fixed-size array.

Contents

• Sliding Window
• Two Pointers
• String Matching
• String Manipulation
• Parsing

Sliding Window

When to use: The problem asks for “longest substring without repeating characters”, “minimum window containing all characters”, or any contiguous substring optimization with a frequency constraint.

Longest Substring Without Repeating Characters

int lengthOfLongestSubstring(string s) {
    vector<int> cnt(256, 0);
    int dup = 0, best = 0;
    
    for (int l = 0, r = 0; r < s.size(); ++r) {
        dup += (++cnt[(unsigned char)s[r]] == 2);
        
        while (dup > 0) {
            dup -= (--cnt[(unsigned char)s[l++]] == 1);
        }
        
        best = max(best, r - l + 1);
    }
    
    return best;
}

Minimum Window Substring

string minWindow(string s, string t) {
    unordered_map<char, int> need, window;
    for (char c : t) need[c]++;
    
    int left = 0, right = 0;
    int valid = 0;
    int start = 0, len = INT_MAX;
    
    while (right < s.size()) {
        char c = s[right++];
        if (need.count(c)) {
            window[c]++;
            if (window[c] == need[c]) valid++;
        }
        
        while (valid == need.size()) {
            if (right - left < len) {
                start = left;
                len = right - left;
            }
            
            char d = s[left++];
            if (need.count(d)) {
                if (window[d] == need[d]) valid--;
                window[d]--;
            }
        }
    }
    
    return len == INT_MAX ? "" : s.substr(start, len);
}

ID	Title	Link	Solution
3	Longest Substring Without Repeating Characters	Link	Solution
76	Minimum Window Substring	Link	-
424	Longest Repeating Character Replacement	Link	-

Two Pointers

When to use: The problem mentions “palindrome”, “reverse string”, or requires comparing characters from both ends of a string moving inward.

Valid Palindrome

bool isPalindrome(string s) {
    int left = 0, right = s.size() - 1;
    
    while (left < right) {
        while (left < right && !isalnum(s[left])) left++;
        while (left < right && !isalnum(s[right])) right--;
        
        if (tolower(s[left]) != tolower(s[right])) {
            return false;
        }
        left++;
        right--;
    }
    
    return true;
}

Reverse String

void reverseString(vector<char>& s) {
    int left = 0, right = s.size() - 1;
    while (left < right) {
        swap(s[left++], s[right--]);
    }
}

ID	Title	Link	Solution
5	Longest Palindromic Substring	Link	Solution
125	Valid Palindrome	Link	-
344	Reverse String	Link	Solution
647	Palindromic Substrings	Link	Solution
151	Reverse Words in a String	Link	Solution

String Matching

When to use: The problem asks to “find a pattern in text”, mentions “KMP”, or requires efficient O(n+m) substring search instead of brute-force O(n·m).

KMP Algorithm

vector<int> buildKMP(string pattern) {
    int m = pattern.size();
    vector<int> lps(m, 0);
    int len = 0, i = 1;
    
    while (i < m) {
        if (pattern[i] == pattern[len]) {
            lps[i++] = ++len;
        } else {
            if (len != 0) {
                len = lps[len - 1];
            } else {
                lps[i++] = 0;
            }
        }
    }
    
    return lps;
}

int kmpSearch(string text, string pattern) {
    int n = text.size(), m = pattern.size();
    vector<int> lps = buildKMP(pattern);
    int i = 0, j = 0;
    
    while (i < n) {
        if (text[i] == pattern[j]) {
            i++;
            j++;
        }
        
        if (j == m) {
            return i - j; // Found at index i - j
        } else if (i < n && text[i] != pattern[j]) {
            if (j != 0) {
                j = lps[j - 1];
            } else {
                i++;
            }
        }
    }
    
    return -1;
}

ID	Title	Link	Solution
28	Find the Index of the First Occurrence in a String	Link	-

String Manipulation

When to use: The problem says “anagram”, “group anagrams”, “remove duplicates”, or requires rearranging or classifying strings by their character composition.

Group Anagrams

vector<vector<string>> groupAnagrams(vector<string>& strs) {
    unordered_map<string, vector<string>> groups;
    
    for (string& str : strs) {
        string key = str;
        sort(key.begin(), key.end());
        groups[key].push_back(str);
    }
    
    vector<vector<string>> result;
    for (auto& [key, values] : groups) {
        result.push_back(values);
    }
    
    return result;
}

ID	Title	Link	Solution
49	Group Anagrams	Link	-
249	Group Shifted Strings	Link	Solution
893	Groups of Special-Equivalent Strings	Link	Solution
1328	Break a Palindrome	Link	Solution

Remove Duplicates

// Remove All Adjacent Duplicates
string removeDuplicates(string s) {
    string result;
    for (char c : s) {
        if (!result.empty() && result.back() == c) {
            result.pop_back();
        } else {
            result.push_back(c);
        }
    }
    return result;
}

// Remove All Adjacent Duplicates II (k duplicates)
string removeDuplicates(string s, int k) {
    vector<pair<char, int>> st;
    
    for (char c : s) {
        if (!st.empty() && st.back().first == c) {
            st.back().second++;
            if (st.back().second == k) {
                st.pop_back();
            }
        } else {
            st.push_back({c, 1});
        }
    }
    
    string result;
    for (auto& [c, count] : st) {
        result.append(count, c);
    }
    
    return result;
}

ID	Title	Link	Solution
49	Group Anagrams	Link	Solution
1047	Remove All Adjacent Duplicates In String	Link	Solution
1209	Remove All Adjacent Duplicates in String II	Link	Solution

Run-Length Encoding

// Two-pointer grouping for consecutive runs
string runLengthEncode(const string& s) {
    string result;
    for (int j = 0, k = 0; j < (int)s.size(); j = k) {
        while (k < (int)s.size() && s[k] == s[j]) k++;
        result += to_string(k - j) + s[j];
    }
    return result;
}

ID	Title	Link	Solution
38	Count and Say	Link	Solution
443	String Compression	Link	-

Parsing

When to use: The problem says “decode string”, “valid abbreviation”, “nested brackets”, or requires interpreting a string according to grammar rules.

Valid Word Abbreviation

bool validWordAbbreviation(string word, string abbr) {
    int i = 0, j = 0;
    int n = word.size(), m = abbr.size();
    
    while (i < n && j < m) {
        if (isdigit(abbr[j])) {
            if (abbr[j] == '0') return false; // Leading zero
            int num = 0;
            while (j < m && isdigit(abbr[j])) {
                num = num * 10 + (abbr[j] - '0');
                j++;
            }
            i += num;
        } else {
            if (word[i] != abbr[j]) return false;
            i++;
            j++;
        }
    }
    
    return i == n && j == m;
}

Decode String

string decodeString(string s) {
    stack<int> numStack;
    stack<string> strStack;
    string current;
    int num = 0;
    
    for (char c : s) {
        if (isdigit(c)) {
            num = num * 10 + (c - '0');
        } else if (c == '[') {
            numStack.push(num);
            strStack.push(current);
            num = 0;
            current = "";
        } else if (c == ']') {
            int repeat = numStack.top();
            numStack.pop();
            string temp = current;
            current = strStack.top();
            strStack.pop();
            while (repeat--) {
                current += temp;
            }
        } else {
            current += c;
        }
    }
    
    return current;
}

ID	Title	Link	Solution
408	Valid Word Abbreviation	Link	Solution
394	Decode String	Link	Solution

Summary

Pattern	Signal Phrases	Key Idea
Sliding Window	“longest substring”, “minimum window”	Track char frequencies in window
Two Pointers	“palindrome”, “reverse”	Compare from both ends
String Matching	“pattern in text”, “KMP”	Failure function for O(n+m)
Manipulation	“anagram”, “group anagrams”	Sort or frequency count
Parsing	“decode string”, “nested brackets”	Stack-based recursion

More templates

• Beginner’s Guide: LeetCode Beginner’s Guide
• Arrays & Strings (KMP, Manacher): Arrays & Strings
• Stack (decode string): Stack
• Master index: Categories & Templates