Lesson 3 · Linear structures

Strings and Substring Algorithms

Strings are arrays of characters, but their use cases—parsing, searching, and natural language—demand specialized algorithms. Because strings are often immutable, seemingly simple concatenations can hide hidden O(N) penalties.

What a String Actually Holds

A string is a sequence of characters, but the useful definition is more precise: it is a sequence of code units in some encoding, and the gap between those two descriptions is where a large class of bugs lives.

In ASCII, one byte is one character and length counts characters. In UTF-8, a code point takes one to four bytes, so a string of 5 visible characters may occupy 10 bytes. In UTF-16 — used internally by Java, JavaScript, and C# — most characters are one 16-bit unit but emoji and less common scripts take two, called a surrogate pair.

The consequences are concrete. "😀".length is 2 in JavaScript and Java, and 1 in Python 3, which indexes by code point. Reversing a UTF-16 string by swapping units splits surrogate pairs and produces invalid text. Even code-point indexing is not the end of it: a base character plus a combining accent is two code points that render as one grapheme.

For interviews this usually simplifies to ASCII and can be set aside, but the assumption should be stated rather than silently made — 'assuming ASCII lowercase' is a sentence that improves an answer.

Representation differs too. C stores a null-terminated array of bytes, so strlen is O(n) because it scans for the terminator, and this is the source of buffer overflows when the terminator is missing. Most other languages store an explicit length, making the length query O(1) and the string able to contain null bytes safely.

Strings are sequences of code units, which are not always characters
UTF-16 stores emoji as two units — length does not count characters
C uses null termination, so strlen is O(n); most languages store a length
State the ASCII assumption rather than making it silently

Immutability and the Quadratic Trap

In Java, Python, C#, and JavaScript, strings are immutable: no operation changes an existing string, it produces a new one. Immutability buys real advantages — strings can be shared without defensive copying, hashed once and cached, and used safely as map keys and across threads.

It also creates the most common performance bug in string code. Building a string by repeated concatenation in a loop looks linear and is not.

Each result += piece allocates a new string and copies everything accumulated so far. Appending n pieces copies 1 + 2 + 3 + … + n characters, which is O(n²). For a thousand pieces that is half a million copies; for a hundred thousand it is five billion, and the program appears to hang.

The fix is to accumulate in a mutable buffer and convert once at the end: StringBuilder in Java, StringBuilder in C#, a list of pieces plus a single join in Python, or strings.Builder in Go. The total work becomes O(n), and the change is usually two lines.

This is worth recognising on sight, because the quadratic version is what most people write first and it passes every small test. CPython does optimise some in-place += cases when the string has one reference, which makes the trap worse — it works acceptably in a script and collapses when the same code runs on real input.

Immutability also means slicing costs. Taking a substring in Java or Python allocates and copies O(k) characters. An algorithm that slices inside a loop can be quietly quadratic even without concatenation, which is why passing index ranges rather than substrings is the standard fix in recursive string algorithms.

Where the cost hides in string operations
Operation	Cost	Note
Index a character	O(1)	O(n) if the encoding is variable-width
Concatenate two strings	O(n + m)	A new allocation every time
Build in a loop with `+=`	O(n²)	The classic trap
Build with a builder or join	O(n)	Always prefer this
Slice a substring	O(k)	Pass index ranges instead
Compare two strings	O(n)	Length check first — often O(1)

Immutable strings make every edit a fresh allocation
+= in a loop copies everything each time — O(n²)
Use a builder, or collect pieces and join once
Slicing allocates too; pass indices in recursive code

The Two-Pointer Shape

A large family of string problems reduces to two indices moving through the string, and recognising the shape is most of the work.

Palindromes are the clearest case. Place one index at each end, compare the characters, and step inward. On a mismatch the string is not a palindrome; if the pointers cross, it is. This is O(n) time and O(1) space — strictly better than the common shortcut of comparing the string with its reverse, which allocates a whole second string.

Real palindrome problems add a filtering rule: ignore non-alphanumeric characters and case. Handle that inside the pointer movement — advance each pointer past characters that do not count, then compare the normalised values — rather than building a cleaned copy first. Same answer, no extra allocation, and it is the version interviewers are looking for.

Reversal is the same skeleton with a swap instead of a comparison, which requires a mutable representation — a character array in Java, a list in Python.

The expand around centre variant finds the longest palindromic substring by running the two pointers outward from each possible centre. There are 2n − 1 centres, counting the gaps between characters for even-length palindromes, and each expansion is O(n), giving O(n²) overall with O(1) space. Forgetting the even-length centres is the standard bug and silently misses half the answers.

Same-direction two pointers handle in-place compaction: a read index scanning everything and a write index marking where the next kept character goes. This removes characters, deduplicates, or compresses runs in one O(n) pass without allocating.

Palindrome: compare from both ends inward, O(1) space
Filter inside the pointer movement, not by building a cleaned copy
Expand around centre needs 2n − 1 centres, not n
Read and write pointers compact in place in one pass

Key reference

Terms, operations, and practical uses

Core vocabulary

Character EncodingA standard (like ASCII or UTF-8) that assigns numerical values to characters so they can be stored in memory.
ImmutabilityA property where an object's state cannot be modified after it is created. Any 'modification' actually returns a new object.
SubstringA contiguous sequence of characters within a string (e.g., 'ell' is a substring of 'hello').

Algorithms

KMP AlgorithmA pattern matching algorithm that preprocesses the search word to avoid re-evaluating matched characters, running in O(N+M) time.
Rabin-KarpA pattern matching algorithm that uses a rolling hash function to quickly filter out impossible matches.
Two PointersA common technique for string problems like checking palindromes by moving pointers from both ends towards the center.

Best practices

String BuildersMutable objects used to efficiently construct strings by appending characters without allocating new memory each time.
Character ArraysConverting an immutable string into an array of characters (e.g., list(str)) to perform in-place modifications.
O(1) Length CheckMost modern languages store the length of the string as a property, making len(str) an O(1) operation.

Implementation

Check if a string is a palindrome

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

def is_anagram(a, b):
    counts = {}
    for ch in a:
        counts[ch] = counts.get(ch, 0) + 1
    for ch in b:
        if counts.get(ch, 0) == 0:
            return False
        counts[ch] -= 1
    return True

ok, _ = is_palindrome('racecar')
bad, steps = is_palindrome('hello')          # 'h' vs 'o' fails immediately
anagram = is_anagram('listen', 'silent')

print(f"{ok} · {bad} after {steps} comparison · {'anagram' if anagram else 'not an anagram'}")

#include <iostream>
#include <string>
#include <unordered_map>
using namespace std;
bool isPalindrome(const string& s, int& comparisons) {
    int left = 0, right = (int)s.size() - 1;
    comparisons = 0;
    while (left < right) {
        comparisons++;
        if (s[left] != s[right]) return false;
        left++;
        right--;
    }
    return true;
}
bool isAnagram(const string& a, const string& b) {
    unordered_map<char, int> counts;
    for (char ch : a) counts[ch]++;
    for (char ch : b) {
        if (counts[ch] == 0) return false;
        counts[ch]--;
    }
    return true;
}
int main() {
    int c1 = 0, steps = 0;
    bool ok = isPalindrome("racecar", c1);
    bool bad = isPalindrome("hello", steps); // 'h' vs 'o' fails immediately
    bool anagram = isAnagram("listen", "silent");
    cout << (ok ? "True" : "False") << " · " << (bad ? "True" : "False")
    << " after " << steps << " comparison · "
    << (anagram ? "anagram" : "not an anagram") << '\n';
}

import java.util.HashMap;
import java.util.Map;
class Main {
    static int comparisons = 0;
    static boolean isPalindrome(String s) {
        int left = 0, right = s.length() - 1;
        comparisons = 0;
        while (left < right) {
            comparisons++;
            if (s.charAt(left) != s.charAt(right)) return false;
            left++;
            right--;
        }
        return true;
    }
    static boolean isAnagram(String a, String b) {
        Map<Character, Integer> counts = new HashMap<>();
        for (char ch : a.toCharArray()) counts.merge(ch, 1, Integer::sum);
        for (char ch : b.toCharArray()) {
            if (counts.getOrDefault(ch, 0) == 0) return false;
            counts.merge(ch, -1, Integer::sum);
        }
        return true;
    }
    public static void main(String[] args) {
        boolean ok = isPalindrome("racecar");
        boolean bad = isPalindrome("hello"); // 'h' vs 'o' fails immediately
        int steps = comparisons;
        boolean anagram = isAnagram("listen", "silent");
        System.out.println(ok + " · " + bad + " after " + steps + " comparison · "
        + (anagram ? "anagram" : "not an anagram"));
    }
}

Watch it run

Step through it

Running on string = 'racecar'

Output

Read all 12 Steps

Two pointers, both ends left starts at index 0 and right at index 6. No reversed copy is allocated — that is the whole advantage of this method over reverse-and-compare.
Compare 'r' and 'r' They match, so the outermost pair is consistent with a palindrome. Move both pointers inward one step.
Compare 'a' and 'a' Match again at indices 1 and 5. Every matching pair shrinks the unverified middle by two characters.
Compare 'c' and 'c' Indices 2 and 4 match. Only the centre character is left unchecked.
Pointers meet at the centre left and right have converged on index 3. A single middle character has nothing to be compared against, so the scan is finished.
Result: palindrome Every pair matched, so 'racecar' reads identically in both directions. Four comparisons for seven characters — roughly n/2, which is O(n).
Now a non-palindrome: 'racecat' Change the last character. The method's value is that it does not need to finish to know the answer.
First comparison already fails 'r' against 't' — no match. The function returns False immediately, after one comparison, without examining the other five characters.
Why early exit matters Reverse-and-compare always does O(n) work building the reversed string before any comparison happens. Two pointers can answer in one step. Same worst case, much better common case, and no extra allocation.
The related shape: anagrams 'listen' and 'silent' contain identical characters in a different order. Two pointers cannot help here — position is exactly what does not matter — so the tool changes to counting.
Count the first string Walk 'listen' once and tally each character: l:1 i:1 s:1 t:1 e:1 n:1. One pass, and the table is bounded by the alphabet, not the input length.
Cancel with the second Walk 'silent' decrementing each count. If any count goes negative the strings differ; here every entry lands exactly on zero, so they are anagrams. O(n) time and O(1) space for a fixed alphabet — beating the O(n log n) of sorting both.

The Counting Shape

The other major family replaces comparison with counting, and applies whenever the question is about which characters are present and how often, rather than about their order.

Anagrams are the archetype. Two strings are anagrams when they contain the same characters with the same multiplicities. Sorting both and comparing works at O(n log n); counting characters in one and decrementing with the other is O(n) — and unequal lengths let you reject in O(1) before counting anything.

The counting structure matters more than it appears. For a known small alphabet, a fixed-size array — 26 entries for lowercase letters, 128 for ASCII — beats a hash map substantially: no hashing, no allocation, contiguous memory, and O(1) indexing by c - 'a'. Reach for a hash map only when the alphabet is large or unknown, such as full Unicode.

A useful refinement for the decrement approach: rather than comparing the whole count array at the end, maintain a single integer of how many entries are currently non-zero. Validity becomes an O(1) check instead of an O(26) scan — which matters when the check runs inside a sliding window at every step.

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

Combining counting with a sliding window covers the harder problems in this family — finding all anagrams of a pattern inside a text, or the smallest window containing every required character. The window slides in O(1) per step because a character entering increments one count and a character leaving decrements another, and the validity counter keeps the check constant-time.

Anagram checks count characters in O(n) rather than sorting at O(n log n)
Compare lengths first — an O(1) rejection
Fixed-size arrays beat hash maps for known small alphabets
Track how many counts are satisfied to keep window validity O(1)