String Techniques

The problem

You're adding a "clever title" checker to a writing app. It should flag when a title reads the same forwards and backwards — "level", "noon", "race car" (ignoring spaces). Next sprint, the product owner wants more: detect when two words are anagrams of each other, and highlight when one word appears as a subsequence of another.

Three different-sounding features. But squint and they're the same handful of moves on an array of characters, reused. Learn the moves and the whole category of string problems opens up.

A first attempt

For the palindrome check, the tempting move is to reverse the whole string and compare:

def is_palindrome_naive(s):
    return s == s[::-1]      # build a full reversed copy, then compare

Correct, but it allocates a second string as long as the first — O(n) extra memory — and compares all n characters even when the very first and last already disagree. On short titles nobody cares; the point is there's a leaner move that needs no copy at all.

The insight

Most string questions are answered by one of three cheap patterns:

• Two pointers from the ends — for palindromes and reversals: walk one index in from the left and one from the right, comparing as you go. O(1) space, and you can bail the instant they disagree.
• Frequency counting — for anagrams: two words are anagrams exactly when they use the same letters the same number of times. Count letters, compare the counts.
• Two pointers same direction — for subsequences: one pointer scans the big string, one tracks how much of the pattern you've matched.

They all lean on the fact from Strings: a string is just a character array.

How it works

Here's the palindrome check with the two-pointer pattern.

"level"    l  e  v  e  l
           i           j    l == l  ✓
              i     j       e == e  ✓
                 ij         pointers meet -> palindrome

The code

def is_palindrome(s):
    i, j = 0, len(s) - 1
    while i < j:
        if s[i] != s[j]:
            return False
        i += 1
        j -= 1
    return True

function isPalindrome(s: string): boolean {
  let i = 0, j = s.length - 1;
  while (i < j) {
    if (s[i] !== s[j]) return false;
    i++;
    j--;
  }
  return true;
}

boolean isPalindrome(String s) {
    int i = 0, j = s.length() - 1;
    while (i < j) {
        if (s.charAt(i) != s.charAt(j)) return false;
        i++;
        j--;
    }
    return true;
}

#include <string.h>
#include <stdbool.h>

bool is_palindrome(const char *s) {
    int i = 0, j = (int)strlen(s) - 1;
    while (i < j) {
        if (s[i] != s[j]) return false;
        i++;
        j--;
    }
    return true;
}

#include <string>
using namespace std;

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

Complexity

The anagram count is O(1) space because the alphabet is fixed-size — 26 for lowercase letters, 256 for bytes — no matter how long the strings get.

When to use it

Practice

Recap

• Most string problems reduce to three reusable patterns: two pointers from the ends (symmetry), frequency counting (anagrams), and two pointers same direction (subsequence).
• The palindrome check runs in O(n) time and O(1) space and bails at the first mismatch — no reversed copy needed.
• Frequency counting is O(1) space because the alphabet is a fixed size regardless of input length.