Lesson 9 · Core algorithms

String Manipulation Techniques

String questions become simpler when classified by the state they need: two pointers for symmetric edits, counters for multiplicity, sliding windows for contiguous constraints, and stacks for nested structure.

Settle the Representation First

Before choosing a technique, three questions about the input decide what the code can assume, and answering them aloud is worth marks in an interview.

What is the alphabet? Lowercase English letters permit a 26-entry count array and c - 'a' indexing. Full ASCII needs 128. Arbitrary Unicode needs a hash map, and raises the question of whether the string's length counts characters at all — in Java and JavaScript it counts UTF-16 code units, so an emoji has length 2, while Python 3 indexes by code point.

Is the string mutable? In Java, Python, C# and JavaScript strings are immutable, so every operation allocates. In C and C++ a character array can be modified in place, which makes O(1)-space algorithms genuinely possible rather than notional.

That immutability creates the most common performance bug in string code. Building a result with result += piece in a loop copies everything accumulated so far on each iteration, giving O(n²). Appending a thousand pieces performs half a million character copies; a hundred thousand pieces performs five billion, and the program appears to hang. The fix is a mutable buffer — StringBuilder, or a list of pieces joined once at the end — which restores O(n).

Slicing costs too. Taking a substring allocates and copies O(k) characters in most languages, so a recursive algorithm that slices at each level is quietly quadratic even without concatenation. Passing index ranges instead of substrings is the standard fix.

The last question is what counts as equal: is the comparison case-sensitive, and do non-alphanumeric characters participate? Deciding this before writing the loop avoids the retrofitted if statements that turn a clean two-pointer scan into something unreadable.

Alphabet size decides between a count array and a hash map
+= in a loop is O(n²) on immutable strings — use a builder
Slicing allocates; pass index ranges in recursive code
Fix the case and filtering rules before writing the comparison

Two Pointers: Symmetry and Compaction

A large family of string problems reduces to two indices, in one of two arrangements.

Converging pointers start at opposite ends and move inward. Reversal swaps the two ends and steps in, requiring a mutable representation and running in O(n) time, O(1) space. Palindrome checking compares rather than swaps, returning false on the first mismatch and true if the pointers cross.

The palindrome variant is worth doing properly. Real problems ask to ignore case and non-alphanumeric characters, and the right approach is to advance each pointer past the characters that do not count, inside the loop, then compare the normalised values. The tempting alternative — building a cleaned copy first — allocates O(n) and is the version interviewers are looking to see you avoid.

Comparing a string with its reverse is another shortcut worth declining: it is correct but allocates a whole second string where two indices need none.

Expand around centre runs the pointers outward to find the longest palindromic substring. There are 2n − 1 centres — n characters plus n−1 gaps between them — and forgetting the gaps silently misses every even-length palindrome. Each expansion is O(n), giving O(n²) overall with O(1) space, which is the expected answer; Manacher's algorithm achieves O(n) but is rarely required.

Same-direction pointers split the work differently: a read index visits every character while a write index marks where the next kept character goes. This compacts in place — removing characters, deduplicating, collapsing runs — in one O(n) pass with no allocation. The write index never overtakes the read index, which is what makes overwriting safe.

String compression — turning aabcccc into a2b1c4 — is this shape with a run counter, and it carries a detail worth noticing: return the original when the 'compressed' form is longer.

Reversal and palindromes converge from both ends in O(1) space
Filter inside the pointer movement, not by building a cleaned copy
Expand-around-centre needs 2n − 1 centres, including the gaps
Read and write pointers compact in place in one pass

Counting: Anagrams and Windows

When the question is about which characters are present and how often rather than their order, the technique is counting.

Anagram testing. Sorting both strings and comparing is O(n log n) and easy to state. Counting is O(n): tally the characters of the first string, decrement with the second, and check that every count returns to zero. Comparing lengths first rejects most non-anagrams in O(1) before any counting begins.

The counting structure matters. For a known small alphabet, a fixed-size array — 26 or 128 entries — beats a hash map substantially: no hashing, no allocation, contiguous memory, O(1) indexing. Reach for a map only when the alphabet is large or unknown.

Grouping anagrams uses the same idea as a key into a hash map. Either the sorted characters or the count vector rendered as a string identifies an anagram class. The count-vector key is O(n) per word against sorting's O(n log n), and is the better choice for long words.

Sliding window combines counting with two same-direction pointers, and covers the harder problems in this family: the longest substring without repeating characters, all anagrams of a pattern within a text, the smallest window containing every required character.

One design decision determines whether these solutions are actually linear. If checking the window's validity means iterating the frequency map, each step is O(alphabet) and the algorithm is O(n · k). Maintaining a single integer — how many distinct characters currently satisfy their requirement — makes validity an O(1) test and the whole algorithm O(n). This is the detail that separates a passing solution from an optimal one.

For counting problems resisting a direct window, the standard reframing is that exactly k equals at most k minus at most k−1, since each of those is a straightforward variable window.

Matching a problem to its shape
The problem says	Shape	Cost
Reverse, palindrome, symmetric	Converging pointers	O(n), O(1) space
Remove, dedupe, compress in place	Read and write pointers	O(n), O(1) space
Anagram, permutation, same characters	Frequency counting	O(n)
Longest or shortest substring with…	Sliding window	O(n)
Longest subsequence, edit distance	Dynamic programming	O(n·m)
Find a pattern in a text	KMP or Rabin–Karp	O(n + m)

Count rather than sort for anagrams — O(n) against O(n log n)
Compare lengths first for an O(1) rejection
Fixed arrays beat hash maps for known small alphabets
Track how many counts are satisfied to keep validity O(1)

Implementation

Two-pointer palindrome check

s = "racecar"
left = 0
right = len(s) - 1
ok = True

while left < right:
    if s[left] != s[right]:
        ok = False
        break
    left += 1
    right -= 1

print("Palindrome:", ok)

#include <iostream>
#include <vector>
#include <queue>
#include <map>
#include <set>
#include <string>
#include <algorithm>
#include <functional>
#include <tuple>
#include <array>
#include <numeric>
using namespace std;
int main()
{
    string s="racecar";
    bool ok=equal(s.begin(),s.begin()+s.size()/2,s.rbegin());
    cout<<"Palindrome: "<<(ok?"True":"False");
}

class Main
{
    public static void main(String[]z)
    {
        String s="racecar";
        boolean ok=true;
        for(int l=0,r=s.length()-1;l<r;l++,r--)if(s.charAt(l)!=s.charAt(r))ok=false;
        System.out.print("Palindrome: "+(ok?"True":"False"));
    }
}

Watch it run

Step through it

Running on mutable characters racecar

Output

Read all 12 Steps

Choose the invariant Symmetric positions must match.
Place left and right left=0 and right=6.
Compare r and r The outer characters agree.
Move inward Advance left and decrement right.
Compare a and a The next pair agrees.
Move inward again Move to indexes 2 and 4.
Compare c and c The third pair agrees.
Pointers meet at e The center needs no partner comparison.
Palindrome confirmed Every required pair matched.
Contrast reversal Reversal would swap these pairs instead.
Contrast anagram An anagram question would compare frequency counts, not positions.
Choose by problem signal Return true for this palindrome.

Substrings, Subsequences, and Parsing

The distinction that decides the algorithm more than any other: a substring is contiguous; a subsequence may skip characters while preserving order.

ace is a subsequence of abcde but not a substring. That difference is not cosmetic — substring problems are usually sliding window or two pointers at O(n), while subsequence problems are usually dynamic programming at O(n·m). Checking which word the problem uses is the fastest way to eliminate half the possible approaches.

The standard subsequence problems are worth recognising on sight. Longest common subsequence builds an O(n·m) table comparing characters and taking the better of two skips on a mismatch. Edit distance is the same table with three operations — insert, delete, replace — and is the basis of spell-checking and diff tools. Is s a subsequence of t is the exception: it needs no table, just two pointers advancing greedily in O(n).

Parsing problems have their own shape. Anything with nesting — brackets, tags, nested expressions — is a stack problem, since the most recently opened construct must close first. Anything scanning tokens with lookahead is a state machine, and writing the states out explicitly beats accumulating conditionals.

Two habits are worth carrying into any string problem. Test the boundaries deliberately: the empty string, a single character, all-identical characters, and the case where the answer is the whole input. These four catch most bugs and cost seconds to check.

And use the library where it is correct. split, join, strip, startsWith and the standard search functions are well tested and usually faster than a hand-written loop. Hand-write only when the problem is explicitly about the algorithm — which, in an interview, it usually is, so say which library call you would use in production before writing the manual version.

Substring means contiguous — window or two pointers, O(n)
Subsequence means skippable — usually DP, O(n·m)
'Is s a subsequence of t' is the greedy two-pointer exception
Nesting means a stack; test empty, single, and all-identical inputs