Strings
Character arrays with their own traps — building, counting, palindromes, matching, and parsing.
Big idea
Strings are sequences of characters, so most problems reuse array tools like two pointers, sliding windows, and frequency counts, with hashing or tries for heavier matching — building a string by repeated concatenation can quietly go quadratic.
Think of it like
A Scrabble player studying a rack of letter tiles is doing string work without realizing it. Checking whether the tiles can spell a word is a letter-count comparison, noticing that "listen" and "silent" use the same tiles is anagram detection, and scanning the board for a gap where a word fits is pattern matching. Strong players don't try every arrangement; they count letters, slide their eyes along a row, and use familiar prefixes to rule words in or out.
Spotting the technique
| Clue | Technique | Where |
|---|---|---|
| "anagram", "same letters", "can be formed from" | count characters | lesson 2 |
| "palindrome" | two ends inward, or expand from the centre | lesson 3 |
| "find the pattern in the text" | matching, rolling hash, KMP | lesson 4 |
| "convert", "parse", "valid number" | careful scanning with an index | lesson 5 |
| "longest substring with/without…" | sliding window | its own topic |
| "words sharing a prefix" | trie | its own topic |
Lessons
- 1Characters and building stringsCharacter codes, immutability, and why += in a loop can cost O(n²).
- 2Counting charactersFrequency arrays and maps answer anagram, "can it be built", and first-unique questions in one pass.
- 3PalindromesCheck from both ends inward; find the longest one by expanding from every centre.
- 4Finding a pattern in textThe naive O(n × m) scan, then Rabin–Karp's rolling hash and KMP's no-backtracking trick.
- 5Parsing and simulationWalk a string with an index, handle each case in order, and test the edges — atoi, versions, compression.