String Processing with Two Pointers

Two Pointers on Strings

The two-pointer technique isn't just for arrays. It's also a powerful tool for processing strings efficiently. Many string manipulation tasks that might seem complex can be simplified by using two indices to traverse the string, often in a single pass. Let's look at a few common problems where this approach shines.

Checking for Palindromes

A palindrome is a word or phrase that reads the same forwards and backwards, like "racecar" or "madam". We can check if a string is a palindrome by comparing characters from both ends simultaneously.

Set one pointer at the beginning of the string (the left pointer) and another at the end (the right pointer). Then, move them toward each other. In each step, compare the characters they point to. If they don't match at any point, the string isn't a palindrome. If they match, continue inward. The process stops when the pointers meet or cross.

#include <string>
#include <iostream>

bool isPalindrome(const std::string& str) {
    int left = 0;
    int right = str.length() - 1;

    while (left < right) {
        // If characters don't match, it's not a palindrome
        if (str[left] != str[right]) {
            return false;
        }
        // Move pointers inward
        left++;
        right--;
    }

    return true; // All characters matched
}

int main() {
    std::string test1 = "racecar";
    std::string test2 = "hello";
    std::cout << test1 << ": " << (isPalindrome(test1) ? "Palindrome" : "Not a Palindrome") << std::endl;
    std::cout << test2 << ": " << (isPalindrome(test2) ? "Palindrome" : "Not a Palindrome") << std::endl;
    return 0;
}

This algorithm runs in $O(N)$ time, where $N$ is the length of the string, because we only iterate through about half of the string once. It also uses constant extra space, $O(1)$ , making it very efficient.

Removing Specific Characters

Imagine you need to remove all occurrences of a specific character from a string, like stripping vowels from "hello world". This task is a great fit for the two-pointer pattern where both pointers move in the same direction.

This approach is often called the "read/write" or "slow/fast" pointer method. One pointer, the write_ptr (slow), keeps track of the end of the processed, valid string. The other, read_ptr (fast), scans through the entire string.

As read_ptr moves, if it encounters a character we want to keep, we copy it to the position of write_ptr and then advance both pointers. If read_ptr finds a character we want to remove, we simply advance read_ptr and leave write_ptr where it is. The character at read_ptr gets overwritten in a future step.

#include <string>
#include <iostream>

void removeChars(std::string& str, char toRemove) {
    int write_ptr = 0;
    for (int read_ptr = 0; read_ptr < str.length(); read_ptr++) {
        // If the character is not the one to remove
        if (str[read_ptr] != toRemove) {
            // Copy it to the write position
            str[write_ptr] = str[read_ptr];
            write_ptr++; // Move write pointer forward
        }
    }
    // Trim the string to its new length
    str.resize(write_ptr);
}

int main() {
    std::string text = "hello world";
    removeChars(text, 'l');
    std::cout << "Result: " << text << std::endl; // Result: heo word
    return 0;
}

After the loop finishes, the string from the beginning up to write_ptr contains the desired result. The rest of the string is garbage, so we resize it. This in-place modification is efficient in both time, $O(N)$ , and space, $O(1)$ .

Reversing Words in a String

What if you need to reverse the order of words in a sentence, like turning "two pointers on strings" into "strings on pointers two"? This is a trickier problem that can be solved elegantly with two layers of two-pointer logic.

The strategy is:

Reverse the entire string. This turns "two pointers on strings" into "sgnirts no sretniop owt".
Iterate through the reversed string with a single pointer. When you find the start and end of a word, use a classic two-pointer reversal (like in our palindrome checker) to reverse just that word. Reversing "sgnirts" gives you "strings", "sretniop" gives "pointers", and so on.

#include <string>
#include <algorithm> // For std::swap
#include <iostream>

// Helper function to reverse a portion of a string
void reverseSubstring(std::string& s, int left, int right) {
    while (left < right) {
        std::swap(s[left], s[right]);
        left++;
        right--;
    }
}

void reverseWords(std::string& s) {
    // 1. Reverse the entire string
    reverseSubstring(s, 0, s.length() - 1);

    int start = 0;
    for (int end = 0; end < s.length(); end++) {
        // Find the end of a word
        if (s[end] == ' ') {
            // 2. Reverse the word found
            reverseSubstring(s, start, end - 1);
            // Move start to the beginning of the next word
            start = end + 1;
        }
    }
    
    // 3. Reverse the last word
    reverseSubstring(s, start, s.length() - 1);
}

int main() {
    std::string sentence = "two pointers on strings";
    reverseWords(sentence);
    std::cout << sentence << std::endl; // strings on pointers two
    return 0;
}

By combining these steps, we solve the problem in-place with $O(N)$ time complexity. Each character is touched a constant number of times: once for the full reversal and once for the word reversal.

Ready to test your understanding?

Quiz Questions 1/5

When checking if the string "LEVEL" is a palindrome using a left pointer starting at index 0 and a right pointer at index 4, what are their positions just before the final comparison?

Quiz Questions 2/5

In the 'read/write' pointer method for removing characters from a string, what happens when the read_ptr encounters a character that should be removed?

These examples show just a few ways the two-pointer technique can be adapted to handle common string problems with great efficiency.

Mastering the Double Pointer Algorithm in C++