[/learnings]

DSA: String Manipulation and Matching

Saturday, 29 August 2026

Learning about the cost model of strings, frequency vectors as window state, bytes vs characters, and rolling hashes for O(1) substring comparison with leetcode questions for practice.

{data-structures-and-algorithms}{strings}

Strings

A string looks like an array of characters, and most of the techniques already covered i.e. two pointers, sliding window, hashing apply to it unchanged.

The Cost Model

An int[] tells the truth about what an operation costs. A string does not, because the language hides allocation behind + and substr.

Concatenation in a loop is quadratic

// O(n^2) - `out + p` builds a whole new string every iteration
string join(const vector<string> &parts) {
  string out;
  for (const auto &p : parts) out = out + p;
  return out;
}

// O(n) - `+=` grows the same buffer, geometrically
string join(const vector<string> &parts) {
  size_t total = 0;
  for (const auto &p : parts) total += p.size();

  string out;
  out.reserve(total);
  for (const auto &p : parts) out += p;
  return out;
}

substr copies, it does not view

// O(n*m) with an allocation per iteration
for (int i = 0; i + m <= n; i++)
  if (s.substr(i, m) == pattern) found(i);

// O(n*m) with zero allocations
for (int i = 0; i + m <= n; i++)
  if (s.compare(i, m, pattern) == 0) found(i);

Rolling Hash

The one matching tool worth learning at this stage, because it is short and it turns “are these two substrings equal” into an O(1) question after O(n) preprocessing.

Treat the string as a number in base B: h[i+1] = h[i] * B + s[i], all modulo a large prime. Then the hash of any substring falls out of a prefix subtraction, exactly like a prefix sum.

struct SubstrHash {
  static const unsigned long long M = (1ULL << 61) - 1;
  vector<unsigned long long> h, p;
  unsigned long long B;

  // multiply mod 2^61 - 1 without overflowing
  static unsigned long long mul(unsigned long long a, unsigned long long b) {
    __uint128_t c = (__uint128_t)a * b;
    unsigned long long lo = (unsigned long long)(c & M);
    unsigned long long hi = (unsigned long long)(c >> 61);
    lo += hi;
    return lo >= M ? lo - M : lo;
  }

  SubstrHash(const string &s, unsigned long long base) : B(base) {
    int n = s.size();
    h.assign(n + 1, 0);
    p.assign(n + 1, 1);
    for (int i = 0; i < n; i++) {
      h[i + 1] = (mul(h[i], B) + (unsigned char)s[i]) % M;
      p[i + 1] = mul(p[i], B);
    }
  }

  // hash of s[l..r], inclusive
  unsigned long long get(int l, int r) const {
    return (h[r + 1] + M - mul(h[l], p[r - l + 1])) % M;
  }
};

mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
unsigned long long base = rng() % (SubstrHash::M - 300) + 256;

Tradeoffs

Equal hashes do not prove equal strings, they make it overwhelmingly likely. For q compared pairs and modulus M the birthday bound puts the collision chance at roughly q^2 / 2M. With M = 2^61 - 1 and a million comparisons that is about 10^-7. With M = 1e9 + 7 it is closer to a coin flip, which is why the textbook base = 31, mod = 1e9 + 7 is not good enough at scale.

Two more rules: map characters to values >= 1, otherwise "a", "aa" and "aaa" all hash to the same thing, and pick the base at runtime rather than compile time, since a fixed base can be defeated by adversarial input.

Complexity

  • Time Complexity
    • Preprocessing: O(n)
    • Substring hash: O(1)
    • Substring equality: O(1) probabilistic, O(n) if you verify the match
  • Space Complexity: O(n)

Leetcode Practice

Cost model and building

Two pointers on strings

Canonical form

Parsing and simulation

Rolling hash

quantinium © 2026