String Two-Pointer Problems

String Two-Pointer Problems

Many string problems compare characters at two positions and move those positions based on what they find. Keeping two indexes (pointers) instead of building new strings gives O(n) time and O(1) extra space, where the naive approach (reverse the string, try every substring) costs extra memory or O(n²) time.

There are two shapes of two pointers on strings:

1. Opposite ends, moving inward: palindromes and in-place reversal.
2. Same direction, as a window: substrings that must contain or avoid certain characters (covered briefly here, in depth in Sliding Window Pattern).

Valid Palindrome (ignoring case and punctuation)

public boolean isPalindrome(String s) {
    int left = 0, right = s.length() - 1;
    while (left < right) {
        while (left < right && !Character.isLetterOrDigit(s.charAt(left)))  left++;   // skip noise
        while (left < right && !Character.isLetterOrDigit(s.charAt(right))) right--;
        if (Character.toLowerCase(s.charAt(left)) != Character.toLowerCase(s.charAt(right))) return false;
        left++;
        right--;
    }
    return true;
}

Why this beats "clean the string, then compare it with its reverse": no new strings are allocated, and it stops at the first mismatch instead of always processing the whole input. Note the left < right guard inside the skip loops. Without it, a string of only punctuation walks the pointers past each other and out of bounds.

Valid Palindrome II: at most one deletion

At the first mismatch you don't know which side's character is the extra one, so try both. Each check is a plain palindrome test on the remaining range:

public boolean validPalindrome(String s) {
    int l = 0, r = s.length() - 1;
    while (l < r) {
        if (s.charAt(l) != s.charAt(r)) {
            return isPalindrome(s, l + 1, r) || isPalindrome(s, l, r - 1);   // skip left OR skip right
        }
        l++;
        r--;
    }
    return true;
}

private boolean isPalindrome(String s, int l, int r) {
    while (l < r) if (s.charAt(l++) != s.charAt(r--)) return false;
    return true;
}

It's still O(n): the outer loop and one of the inner checks each cover the string once. Allowing k deletions turns this into a DP / longest-palindromic-subsequence problem. The branching approach explodes exponentially.

Reversal in place

public void reverse(char[] s) {
    for (int l = 0, r = s.length - 1; l < r; l++, r--) {
        char t = s[l]; s[l] = s[r]; s[r] = t;
    }
}

Reverse the words of a sentence, in place

The classic trick uses reversal twice: reverse the whole string, then reverse each word back.

"the sky is blue"  → reverse all  → "eulb si yks eht"  → reverse each word → "blue is sky the"

public String reverseWords(String s) {
    char[] c = s.trim().replaceAll("\\s+", " ").toCharArray();   // normalize spaces first
    reverse(c, 0, c.length - 1);
    for (int start = 0, i = 0; i <= c.length; i++) {
        if (i == c.length || c[i] == ' ') {
            reverse(c, start, i - 1);
            start = i + 1;
        }
    }
    return new String(c);
}

private void reverse(char[] c, int l, int r) {
    while (l < r) { char t = c[l]; c[l++] = c[r]; c[r--] = t; }
}

In an interview, String.join(" ", reversed(split(...))) is acceptable if the interviewer allows extra space. The in-place version is what they ask for as the follow-up ("what if the input were a mutable char array and you had O(1) extra space?").

Longest palindromic substring: expand around centres

The pointers can also start in the middle and move outward. Every palindrome is symmetric around its centre, which is either a character (odd length) or the gap between two characters (even length). There are 2n − 1 centres. Expand from each while the ends match:

public String longestPalindrome(String s) {
    int bestStart = 0, bestLen = 0;
    for (int centre = 0; centre < s.length(); centre++) {
        int odd  = expand(s, centre, centre);        // "aba"
        int even = expand(s, centre, centre + 1);    // "abba"
        int len = Math.max(odd, even);
        if (len > bestLen) {
            bestLen = len;
            bestStart = centre - (len - 1) / 2;
        }
    }
    return s.substring(bestStart, bestStart + bestLen);
}

private int expand(String s, int l, int r) {
    while (l >= 0 && r < s.length() && s.charAt(l) == s.charAt(r)) { l--; r++; }
    return r - l - 1;                                  // length of the palindrome found
}

O(n²) time and O(1) space. It's simpler and faster in practice than the O(n²)-space DP table. (Manacher's algorithm does it in O(n), and is worth naming but rarely expected.)

Merging two sorted strings or sequences

Two pointers, one per input, always taking the smaller current element. It's the merge step of merge sort:

String mergeSorted(String a, String b) {
    StringBuilder out = new StringBuilder(a.length() + b.length());
    int i = 0, j = 0;
    while (i < a.length() && j < b.length()) out.append(a.charAt(i) <= b.charAt(j) ? a.charAt(i++) : b.charAt(j++));
    out.append(a, i, a.length()).append(b, j, b.length());
    return out.toString();
}

The same shape solves "is s a subsequence of t?": advance t's pointer always, and advance s's pointer only on a match. s is a subsequence if its pointer reaches the end.

Same-direction pointers: Minimum Window Substring

The right pointer expands the window until it's valid, then the left pointer shrinks it while it stays valid, recording the smallest window seen:

public String minWindow(String s, String t) {
    int[] need = new int[128];
    for (char c : t.toCharArray()) need[c]++;
    int missing = t.length(), bestStart = 0, bestLen = Integer.MAX_VALUE;

    for (int left = 0, right = 0; right < s.length(); right++) {
        if (need[s.charAt(right)]-- > 0) missing--;          // this char was still needed
        while (missing == 0) {                               // window contains all of t
            if (right - left + 1 < bestLen) { bestLen = right - left + 1; bestStart = left; }
            if (++need[s.charAt(left++)] > 0) missing++;     // removing a needed char breaks validity
        }
    }
    return bestLen == Integer.MAX_VALUE ? "" : s.substring(bestStart, bestStart + bestLen);
}

need[c] going negative means "we have more of c than required". Each pointer moves at most n times, so this is O(|s| + |t|).

Follow-up questions this topic invites — and their answers

Q: Why not reverse the string and compare to check a palindrome? A: It works, but allocates O(n) extra memory and always processes the whole string. Two pointers use O(1) space and stop at the first mismatch. For the "ignore punctuation" version, the reverse approach also needs a cleaned copy first.

Q: What changes if up to k deletions are allowed? A: Branching at each mismatch becomes exponential. Instead, compute the longest palindromic subsequence (a DP, O(n²)) and check whether n − LPS ≤ k.

Q: How do you handle Unicode (emoji, accents) in palindrome checks? A: Iterate over code points instead of chars, since emoji are two chars, and consider Unicode normalization (NFC) so that "é" written as one code point or as "e" + accent compares equal. For interview problems limited to ASCII, state that assumption.

Q: Why does Minimum Window Substring run in linear time with a nested loop? A: Each pointer only moves forward, and each moves at most n times in total. The inner while doesn't restart for each right, so total work is O(n + m), not O(n²).

Q: Expand-around-centre vs DP for the longest palindromic substring? A: Both are O(n²) time, but expanding uses O(1) extra space versus O(n²) for the DP table, and it's usually faster in practice. The DP is worth knowing because the same table answers "is s[i..j] a palindrome?" for all ranges, which some follow-up problems need, such as palindrome partitioning.