Week 4: String Algorithms

1. std::string Essentials & Common Gotchas

A std::string is a dynamically-sized, mutable, contiguous array of characters — mechanically closer to vector<char> than to an immutable string type from other languages. That mutability and the underlying contiguous buffer are exactly why every array technique from Weeks 2–3 (two pointers, sliding window, sorting characters) applies to strings without modification.

string_basics.cpp

#include <string>
#include <iostream>
using namespace std;

int main() {
    string s = "hello world";
    s += "!";                       // append -- amortized O(1)
    s.push_back('?');               // append a single char
    string sub = s.substr(0, 5);    // "hello" -- O(k) copy, k = substring length
    size_t pos = s.find("world");   // O(n*m) worst case; returns string::npos if absent

    if (pos != string::npos) {
        cout << "found at index " << pos << "\n";
    }

    for (char c : s) {              // iterate characters directly
        if (c == ' ') continue;
    }
}

Two gotchas trip up almost everyone at first. First, s[i] on an out-of-range i is undefined behavior — it will not throw, it will just silently read invalid memory; use s.at(i) during debugging if you want a thrown exception on an out-of-bounds index instead. Second, building a string with repeated += inside a loop looks like O(1) per append, but each concatenation can trigger a full reallocation and copy of the growing buffer, making naive repeated concatenation O(n²) overall for n appends — call s.reserve(expectedSize) up front, or build into an ostringstream, when you know you're constructing a large string.

Convert between numbers and strings with to_string/stoi

to_string(x) converts a number to a string, and stoi(s) (or stol, stoll for wider types) parses a string back to a number, throwing invalid_argument if the string isn't a valid number. These come up constantly when a problem's input or output format mixes numeric and string data.

2. Palindrome Checks & Expand-Around-Center

A string is a palindrome if it reads the same forwards and backwards — the two-pointer check from Week 2 applies directly, closing pointers from both ends until they meet:

is_palindrome.cpp

#include <string>
using namespace std;

// O(n) time, O(1) space.
bool isPalindrome(const string& s) {
    int left = 0, right = (int)s.size() - 1;
    while (left < right) {
        if (s[left] != s[right]) return false;
        left++;
        right--;
    }
    return true;
}

Finding the longest palindromic substring is a different question: rather than checking one whole string, you check every possible center. Every palindrome has a center — either a single character (odd length) or a gap between two characters (even length) — so expanding outward from each of the 2n−1 possible centers, stopping as soon as the characters no longer match, finds the longest palindrome touching that center:

longest_palindromic_substring.cpp

#include <string>
using namespace std;

// Expands outward from (left, right) while the characters match, and returns the
// resulting palindrome. Call with (i, i) for an odd-length center, (i, i+1) for even.
string expandAroundCenter(const string& s, int left, int right) {
    while (left >= 0 && right < (int)s.size() && s[left] == s[right]) {
        left--;
        right++;
    }
    return s.substr(left + 1, right - left - 1);
}

// O(n^2) time (n centers, each expansion up to O(n)), O(1) extra space aside
// from the returned result.
string longestPalindromicSubstring(const string& s) {
    string best = "";
    for (int i = 0; i < (int)s.size(); i++) {
        string odd = expandAroundCenter(s, i, i);
        string even = expandAroundCenter(s, i, i + 1);
        if (odd.size() > best.size()) best = odd;
        if (even.size() > best.size()) best = even;
    }
    return best;
}

Always check both center types

Forgetting the even-length center call — expandAroundCenter(s, i, i + 1) — is the single most common bug in this pattern. "aa" has no single-character center, only the gap between its two characters, so a solution that only expands from (i, i) will silently miss every even-length palindrome.

3. String Hashing (Rolling Hash)

Comparing two substrings character-by-character costs O(length) every time. A rolling hash precomputes a hash value for every prefix of the string in O(n), so that the hash of any substring can be derived in O(1) — letting you check whether two substrings are equal (with very high probability) in constant time after a linear-time setup.

rolling_hash.cpp

#include <string>
#include <vector>
using namespace std;

const long long MOD = 1'000'000'007;
const long long BASE = 131;

struct RollingHash {
    vector<long long> prefixHash;  // prefixHash[i] = hash of s[0..i-1]
    vector<long long> basePow;     // basePow[i]   = BASE^i mod MOD

    explicit RollingHash(const string& s) {
        int n = (int)s.size();
        prefixHash.assign(n + 1, 0);
        basePow.assign(n + 1, 1);
        for (int i = 0; i < n; i++) {
            prefixHash[i + 1] = (prefixHash[i] * BASE + s[i]) % MOD;
            basePow[i + 1] = (basePow[i] * BASE) % MOD;
        }
    }

    // Hash of s[l..r] inclusive, in O(1).
    long long hashRange(int l, int r) const {
        long long h = prefixHash[r + 1] - (prefixHash[l] * basePow[r - l + 1]) % MOD;
        return ((h % MOD) + MOD) % MOD;   // keep the result non-negative
    }
};

With a RollingHash built once in O(n), checking whether s[a..a+len-1] equals s[b..b+len-1] becomes two hashRange calls and an integer comparison — O(1) instead of O(len).

Hashing gives probabilistic, not guaranteed, equality

Two different substrings can, in rare cases, collide to the same hash under a single modulus — a false positive. For interview-level problems a single 64-bit-safe modulus is usually treated as good enough, but if correctness must be exact, compute two independent rolling hashes with different bases and moduli and require both to match, which makes an undetected collision astronomically unlikely.

4. Basic Pattern Matching: Naive and KMP

Pattern matching asks: where does a pattern of length m occur inside a text of length n? The naive approach tries every starting position and compares character-by-character, giving it a worst case of O(n·m) — for example, searching for "aaab" in a text of all as re-examines almost the whole pattern at every position before failing:

naive_search.cpp

#include <string>
#include <vector>
using namespace std;

// Returns every starting index where pattern occurs in text. O(n*m) worst case.
vector<int> naiveSearch(const string& text, const string& pattern) {
    vector<int> matches;
    int n = (int)text.size(), m = (int)pattern.size();
    for (int i = 0; i + m <= n; i++) {
        int j = 0;
        while (j < m && text[i + j] == pattern[j]) j++;
        if (j == m) matches.push_back(i);
    }
    return matches;
}

KMP (Knuth-Morris-Pratt) gets to O(n + m) by never re-examining a character of the text once it's been matched. It precomputes an LPS array ("longest proper prefix of pattern[0..i] that is also a suffix of it") — when a mismatch happens after some partial match, the LPS array tells you exactly how far you can safely shift the pattern without re-checking characters you already know match:

kmp_search.cpp

#include <string>
#include <vector>
using namespace std;

// lps[i] = length of the longest proper prefix of pattern[0..i] that is also
// a suffix of pattern[0..i]. O(m) time.
vector<int> buildLPS(const string& pattern) {
    int m = (int)pattern.size();
    vector<int> lps(m, 0);
    int len = 0;   // length of the current matching prefix-suffix
    for (int i = 1; i < m; i++) {
        while (len > 0 && pattern[i] != pattern[len]) len = lps[len - 1];
        if (pattern[i] == pattern[len]) len++;
        lps[i] = len;
    }
    return lps;
}

// Returns every starting index where pattern occurs in text. O(n + m) time.
vector<int> kmpSearch(const string& text, const string& pattern) {
    vector<int> matches;
    if (pattern.empty()) return matches;

    vector<int> lps = buildLPS(pattern);
    int n = (int)text.size(), m = (int)pattern.size();
    int i = 0, j = 0;   // i walks the text, j walks the pattern
    while (i < n) {
        if (text[i] == pattern[j]) {
            i++;
            j++;
            if (j == m) {
                matches.push_back(i - j);
                j = lps[j - 1];   // look for the next match, reusing partial info
            }
        } else if (j > 0) {
            j = lps[j - 1];      // fall back without moving i -- this is the speedup
        } else {
            i++;
        }
    }
    return matches;
}

You don't need to memorize KMP's implementation

What interviewers actually care about is the intuition: naive search wastes work by forgetting everything it just learned on a mismatch and restarting one position later, while KMP (or a rolling-hash-based search) reuses that information to guarantee linear time. Being able to state that trade-off, and knowing std::string::find exists for everyday use, matters more than reproducing the LPS recurrence from memory under pressure.

5. Hands-on Exercise

Hands-on

Build a mini text-search utility

Combine palindrome detection, rolling hashing, and pattern matching into one small toolkit, and confirm each optimized version against a brute-force baseline.

Requirements:

Implement isPalindrome and longestPalindromicSubstring via expand-around-center; test on "babad" and confirm it returns a valid longest palindrome ("bab" or "aba").
Implement RollingHash and use hashRange to check whether two given substrings of a string are equal in O(1) after the O(n) build.
Implement naiveSearch, then construct a text/pattern pair (like a long run of as and pattern "aaab") that demonstrates its O(n·m) worst case.
Implement buildLPS and kmpSearch, and verify they return identical match indices to naiveSearch across several test strings, including edge cases like an empty pattern or a pattern longer than the text.
Benchmark naiveSearch vs. kmpSearch with <chrono> on the worst-case input from step 3 at a large size (100,000+ characters) and report the timing difference.

Hint

Print out the LPS array for a pattern like "aabaaab" alongside the pattern itself before wiring it into kmpSearch — seeing where the values jump helps confirm your buildLPS logic is correct before it's buried inside the search loop.

6. Knowledge Check

Four quick questions. Expand each to check your answer.

Why is repeatedly appending to a string with `+=` inside a loop O(n²) overall instead of O(n)?

A std::string is backed by a contiguous buffer, and appends are only O(1) amortized because the buffer doubles in capacity when it fills up — but each individual reallocation still has to copy every existing character into the new buffer. Across n appends where the buffer keeps growing, the total copying work sums to O(n) amortized in the typical case, but if you don't reserve capacity up front and the string is being built alongside frequent reallocation-triggering growth (or worst-case implementations), the pattern can degrade toward O(n²) — which is why reserve() is worth calling when the final size is known.

How does `expandAroundCenter` handle both odd-length and even-length palindromes with the same function?

The function just expands outward from whatever (left, right) pair it's given. Calling it with (i, i) starts both pointers on the same character, which is the center of an odd-length palindrome; calling it with (i, i + 1) starts them on two adjacent characters with a gap between them as the center, which is what an even-length palindrome needs. Trying both calls at every index covers every one of the 2n−1 possible palindrome centers in the string.

What does the LPS (failure function) array let KMP avoid that naive search cannot?

On a mismatch, naive search discards all information about the partial match and restarts comparison one position to the right, potentially re-comparing characters it has already seen. The LPS array records, for every prefix of the pattern, how much of it is both a prefix and a suffix — so on a mismatch, KMP can jump the pattern forward to reuse that already-matched information instead of re-scanning it, which is what keeps the text pointer i moving forward only, and gives the overall O(n + m) bound.

Why use a rolling hash with modulo arithmetic instead of directly comparing substrings each time, and what's the catch?

Direct substring comparison costs O(length) every time you need to check equality, which adds up when you're comparing many substrings (e.g. across all possible starting positions of a sliding window). A rolling hash precomputes prefix hashes in O(n) once, after which any substring's hash — and therefore an equality check between two substrings — is O(1). The catch is that hash equality doesn't guarantee character-for-character equality: two different substrings can collide under a given base and modulus, a rare but real false positive, which is why exact-correctness use cases pair two independent hashes rather than trusting one.