Strings in Depth
Why this exists
Most interview string problems are array problems wearing a different type: count characters, move two pointers, slide a window. That framing is useful, and the earlier lessons in this module use it. But it hides the part of strings that causes real production bugs. A "character" is not a byte. length does not count what a person would call letters. Two strings that render identically can compare unequal. Building a string in a loop can be quadratic. Lowercasing a word gives a different answer in Istanbul than in London. None of this matters for "abc", and all of it matters the first time a user types their name with an accent or sends an emoji.
The history explains the mess. ASCII (1963) fixed 128 characters in 7 bits, enough for English. The next thirty years produced hundreds of incompatible 8-bit "code pages" for every other script. Unicode (1991) set out to give every character in every script one number, a code point, and at first assumed 16 bits would be enough. Java (1995), JavaScript (1995) and Windows NT committed to 16-bit characters on that assumption. Unicode 2.0 (1996) grew the code space to 1,114,112 code points (U+0000 to U+10FFFF), and the 16-bit languages had to bolt on surrogate pairs to reach the rest. Meanwhile Ken Thompson and Rob Pike designed UTF-8 in 1992 as a variable-width, ASCII-compatible byte encoding. By the mid-2010s it carried the large majority of web pages. Today each language's string type is a fossil of the year it was designed: Java and JavaScript think in UTF-16 code units, Python 3 thinks in code points, and C++ thinks in bytes.
This lesson does two jobs. First, it explains what a string is in each of the four course languages, how the encodings work at the byte level, and what immutability costs. Second, it works through the string problem families that interviews and real code keep producing: frequency counting and anagrams, palindromes and reversal, parsing without regex, string building, conversions, and hashing. Pattern-matching algorithms such as KMP get only a preview here, with a link to where they are covered.
Pattern triggers
| If the problem says or has… | Think of… |
|---|---|
| "anagram", "permutation of", "same letters" | A 26-entry count array (or a hash map for big alphabets) |
| "group words that are anagrams" | A canonical key per word: sorted letters or a count tuple, then a hash map |
| "first non-repeating character", "ransom note", "can be built from" | Two passes over a frequency table |
| "palindrome", "reads the same backwards", "ignoring non-alphanumerics" | Two pointers from both ends, skipping filtered characters |
| "reverse the words", "in place" | Reverse the whole string, then reverse each word; compact the spaces |
| "convert string to integer", "validate a number" | A small state machine; check for overflow before multiplying |
| "evaluate / tokenize an expression", "nested brackets", "decode k[...]" | Tokenizer plus a stack |
| "compress", "run-length", "count and say" | One pass with a run start pointer and a builder |
| "zigzag", "write in rows" | Simulate with one builder per row |
| "build a result string in a loop" | A builder (''.join, StringBuilder, std::string::append), never repeated + on immutable strings |
| "length", "character count", user-facing text, emoji | Decide whether you mean bytes, code units, code points or graphemes |
| "case-insensitive compare", "sort names" | casefold or a locale-independent fold; real sorting needs collation |
| "find a pattern in a text" | Naive scan for interviews; KMP, Z or rolling hash for guarantees (String Algorithms) |
| "deduplicate / look up many strings" | Hash them; the hash is cached on immutable strings in Java and Python |
The meta-trigger: as soon as non-ASCII text can appear, stop thinking "array of characters" and ask what unit the problem means. Interview problems usually say "lowercase English letters" to make that question go away. When they do, use the 26-array. When they do not, ask.
Intuition & first principles
Characters, code points, code units, bytes, graphemes
There are five layers, and most bugs come from mixing two of them.
- A grapheme cluster is what a reader perceives as one character:
é,🇮🇳,👨👩👧. It can be several code points. - A code point is Unicode's number for an abstract character, written U+XXXX.
éis U+00E9, and😀is U+1F600. There are 1,114,112 possible code points, of which roughly 150,000 are assigned to characters. - A code unit is the fixed-size chunk an encoding works in: 8 bits for UTF-8, 16 bits for UTF-16, 32 bits for UTF-32.
- An encoding maps code points to sequences of code units. UTF-32 uses one unit per code point. UTF-16 uses one or two. UTF-8 uses one to four.
- Bytes are what actually sits in memory, on disk and on the wire.
The family emoji 👨👩👧 shows how far apart these layers can be. It is one grapheme made of 5 code points (man, zero-width joiner, woman, zero-width joiner, girl). That is 8 UTF-16 code units and 18 UTF-8 bytes. Python reports len = 5, JavaScript reports length = 8, and C++ size() on the UTF-8 bytes reports 18. Every one of those numbers is "correct" for its own layer.
What a string is, per language
Python str is an immutable sequence of Unicode code points. len(s) counts code points, s[i] is the i-th code point (as a length-1 str), and slicing copies. Since Python 3.3 (PEP 393), CPython stores each string in the narrowest fixed width that fits its widest character: 1 byte per code point if everything is Latin-1, 2 bytes if everything is in the Basic Multilingual Plane, otherwise 4. Indexing therefore stays . One emoji in a long ASCII string quadruples its memory. On CPython 3.14, sys.getsizeof of a 100-character string is 141 bytes for ASCII, 258 for 100 € (2 bytes each) and 460 for 100 😀 (4 bytes each). Raw bytes are a separate type, bytes.
Java String is immutable and its API is defined in terms of UTF-16 code units. length() counts code units, and charAt(i) returns a 16-bit char, which for a character outside the BMP is half of a surrogate pair. codePointAt, codePointCount and codePoints() work in code points. Since JDK 9 (JEP 254, Compact Strings), the internal storage is a byte[] plus a coder flag. Strings whose characters all fit in Latin-1 use 1 byte per char, and the rest use 2. This changed memory use, not the API. The hash code is computed lazily and cached in the object.
C++ std::string is a mutable sequence of char, which means bytes. It has no notion of encoding. size() counts bytes, s[i] is a byte, and storing UTF-8 in it is a convention the type does not enforce or understand. Most implementations use a small string optimisation: short strings (up to 15 bytes in libstdc++ and MSVC, 22 in libc++) live inside the object with no heap allocation. std::u16string and std::u32string hold 16- and 32-bit units. std::string_view (C++17) is a non-owning pointer-plus-length view that makes substrings free.
JavaScript strings are immutable sequences of UTF-16 code units. length counts code units, and s[i] and charCodeAt(i) return one unit. "😀".length is 2. String iteration (for...of, spread [...s], Array.from(s)) walks by code point, so [..."😀a"].length is 2. codePointAt reads a full code point at a unit index. Intl.Segmenter splits by grapheme.
flowchart LR
G["grapheme: what a reader sees"] --> CP["code points: Unicode numbers"]
CP --> U8["UTF-8: 1-4 bytes each"]
CP --> U16["UTF-16: 1-2 units each"]
CP --> U32["UTF-32: 1 unit each"]
U8 --> CPP["C++ std::string counts bytes"]
U16 --> JJ["Java and JS length counts units"]
CP --> PY["Python len counts code points"]
UTF-8 byte layout
UTF-8 encodes a code point in 1 to 4 bytes. The number of leading 1-bits in the first byte gives the sequence length, and every continuation byte starts with 10:
| Code point range | Bytes | Byte 1 | Byte 2 | Byte 3 | Byte 4 | Payload bits |
|---|---|---|---|---|---|---|
| U+0000 – U+007F | 1 | 0xxxxxxx | 7 | |||
| U+0080 – U+07FF | 2 | 110xxxxx | 10xxxxxx | 11 | ||
| U+0800 – U+FFFF | 3 | 1110xxxx | 10xxxxxx | 10xxxxxx | 16 | |
| U+10000 – U+10FFFF | 4 | 11110xxx | 10xxxxxx | 10xxxxxx | 10xxxxxx | 21 |
This design gives UTF-8 several useful properties:
- ASCII compatibility. Every ASCII file is already valid UTF-8, and no byte of a multi-byte sequence is below 0x80. Code that searches for
/or\nbyte-by-byte therefore never matches in the middle of a character. - Self-synchronisation. From any byte position, back up over
10xxxxxxbytes to reach a character boundary. - Byte order equals code point order.
strcmpon UTF-8 sorts by code point.
The cost is that the -th code point cannot be found in : you must scan.
Worked example: "é" (U+00E9). 0xE9 is 000 1110 1001 in 11 bits. Split it 5 + 6: 00011 and 101001. Prefix them to get 110 00011 = 0xC3 and 10 101001 = 0xA9. So "é".encode() is b'\xc3\xa9'.
Worked example: "😀" (U+1F600). 0x1F600 is 0 0001 1111 0110 0000 0000 in 21 bits. Split it 3 + 6 + 6 + 6: 000, 011111, 011000, 000000. That gives 11110000 = F0, 10011111 = 9F, 10011000 = 98, 10000000 = 80. In UTF-16 the same code point becomes a surrogate pair. Subtract 0x10000 to get 0xF600, then split the 20 bits 10 + 10: the high surrogate is 0xD800 + 0x3D = 0xD83D and the low surrogate is 0xDC00 + 0x200 = 0xDE00.
Trace: UTF-8 encoding of "héllo😀". All values were produced by Python's str.encode('utf-8').
| Char | Code point | UTF-8 bytes | Hex | Binary |
|---|---|---|---|---|
| h | U+0068 (104) | 1 | 68 | 01101000 |
| é | U+00E9 (233) | 2 | C3 A9 | 11000011 10101001 |
| l | U+006C (108) | 1 | 6C | 01101100 |
| l | U+006C (108) | 1 | 6C | 01101100 |
| o | U+006F (111) | 1 | 6F | 01101111 |
| 😀 | U+1F600 (128512) | 4 | F0 9F 98 80 | 11110000 10011111 10011000 10000000 |
Totals: 6 code points, 10 UTF-8 bytes, 7 UTF-16 code units (one for each BMP character plus two for the emoji). So len is 6 in Python, length is 7 in Java and JavaScript, and size() of the UTF-8 std::string is 10 in C++.
flowchart TD
B["read byte b"] --> Q1{"b < 0x80 ?"}
Q1 -->|"yes"| One["1-byte char: ASCII"]
Q1 -->|"no"| Q2{"top bits 110 ?"}
Q2 -->|"yes"| Two["read 1 continuation byte"]
Q2 -->|"no"| Q3{"top bits 1110 ?"}
Q3 -->|"yes"| Three["read 2 continuation bytes"]
Q3 -->|"no"| Q4{"top bits 11110 ?"}
Q4 -->|"yes"| Four["read 3 continuation bytes"]
Q4 -->|"no"| Bad["invalid lead byte: error or U+FFFD"]
Normalization
Unicode often gives two ways to write the same text. é can be the single precomposed code point U+00E9, or e (U+0065) followed by COMBINING ACUTE ACCENT (U+0301). The two render identically but are different sequences: lengths 1 and 2, different bytes, == false. Normalization picks a canonical form. NFC composes where possible and is what most keyboards and the web produce. NFD decomposes. NFKC and NFKD additionally fold "compatibility" variants such as fi → fi and full-width digits → ASCII digits. In Python, unicodedata.normalize('NFD', 'é') has length 2 (0x65, 0x301), and normalizing it back to NFC gives a string equal to the original.
Practical rule: normalize at the boundary, when text enters your system, usually to NFC. Then compare, hash and index the normalized form. macOS file systems historically stored file names in a decomposed form, which is a classic source of "file exists but cannot be found" bugs when names cross platforms.
The cost of immutability
Python, Java and JavaScript strings are immutable, so s = s + t allocates a new string and copies both parts. Appending one character times copies characters. For that is 5,000,050,000 character copies, about 5 GB of memory traffic to build a 100 KB string. This is the quadratic concatenation trap.
The fix is a builder: a mutable, growable buffer with amortised append. Its capacity doubles like a dynamic array, so the total copying is . You convert it to a string once at the end:
- Python: collect pieces in a list and
''.join(parts)once. Or useio.StringIO. CPython has an implementation-specific optimisation that resizes a string in place fors += twhen nothing else referencess. Do not rely on it. PEP 8 explicitly warns that it is CPython-only and fragile. - Java:
StringBuilder(orStringBufferif you need synchronization, which you almost never do).javaccompiles a single expressiona + b + cinto one builder (or, since JDK 9, aninvokedynamicStringConcatFactorycall). It does not hoist a builder out of a loop, sos += xinside a loop is still quadratic. - C++:
std::stringis mutable, andappend/+=/push_backare amortised .reserve(n)pre-allocates when you know the size. The trap in C++ iss = s + t, which creates a temporary. Writes += t. - JavaScript:
+=in a loop is usually fine in practice. V8 (and other engines) represent many concatenation results as cons strings, rope nodes that point at both halves without copying. The rope is flattened into a contiguous buffer lazily, when something needs indexed access.parts.push(x)followed byparts.join('')is also linear and is the portable choice. Rope behaviour is an engine optimisation, not a language guarantee, and flattening has its own cost, so benchmark if it matters. The class isConsStringin V8's source (src/objects/string.h).
Substring cost
| Language | s[i:j] / substring | Notes |
|---|---|---|
| Python | copies, | memoryview gives zero-copy slices of bytes, not str |
| Java | copies, , since JDK 7u6 | Before 7u6, substring shared the parent's char[]. That was , but a tiny substring could keep a huge parent alive (a memory leak) |
| C++ | s.substr(i, n) copies; std::string_view(s).substr(i, n) is | A string_view must not outlive the string it views |
| JavaScript | engine-dependent | V8 may create a sliced string that references the parent, with a similar retention risk |
The algorithmic consequence: code that takes substrings inside a loop, such as s[i:] at every step of a recursion, is quietly . Pass indices instead.
Comparison and sorting
Default string comparison in all four languages is lexicographic by code unit: compare position by position, the first difference decides, and a proper prefix is smaller. In Python and C++ (on UTF-8 bytes) that is code point order. In Java and JavaScript it is UTF-16 code-unit order, which differs from code point order for characters above U+FFFF. The surrogates 0xD800–0xDFFF sort below U+E000–U+FFFF. C's strcmp compares bytes as unsigned char.
None of these is how humans sort. sorted(["apple", "Banana", "cherry"]) gives ['Banana', 'apple', 'cherry'] because uppercase letters have smaller code points. Real alphabetical order needs collation: locale-aware rules (the Unicode Collation Algorithm, ICU, Intl.Collator, Java's Collator, SQL COLLATE). Collation can treat é like e at the first level, sort ä after z in Swedish but next to a in German, and ignore case. For case-insensitive equality, use str.casefold() in Python, which handles ß → ss, rather than lower().
Interning, ==, and hash caching
In Java, == on objects compares references. "ab" == "ab" is true only because the compiler interns string literals into a shared pool. new String("ab") == "ab" is false, and so is a string built at runtime. Always use equals. String.intern() forces pooling, which saves memory for many duplicate strings at the cost of a global table. In Python, == compares values and is compares identity. CPython interns some strings, such as identifiers and some short literals, so is sometimes appears to work, but it is never correct for value comparison. JavaScript === and C++ == on std::string compare values.
Immutability also makes hash caching safe. Java's String.hashCode() computes once and stores it in the object, so repeated HashMap lookups with the same key object cost after the first hash, not . CPython caches str hashes too, and randomises them per process (PYTHONHASHSEED) to defeat collision attacks. A mutable string cannot safely cache its hash, which is one reason C++ std::hash<std::string> rehashes on every call. The hash table side is in Hash Tables.
Mechanics
The recurring string techniques, each as a small algorithm.
Frequency counting
For a known small alphabet, an array indexed by ch - 'a' beats a hash map. It does no hashing and no allocation per key, it is cache-resident, and comparing two count arrays is a fixed 26 steps. Use a hash map (Counter, HashMap<Character, Integer>, unordered_map, Map) when the alphabet is large or unknown, for example with Unicode input.
- Valid anagram. If the lengths differ, return false. Increment counts for
s, decrement fort, and check that all counts are zero. time, space for a fixed alphabet. - First unique character. Pass 1 counts. Pass 2 returns the first index whose count is 1.
- Ransom note. Count the magazine, then decrement for each note character and fail if a count goes negative.
Anagram grouping by canonical key
Two words are anagrams exactly when they have the same multiset of letters. Map each word to a canonical key that depends only on that multiset, then bucket by key in a hash map. There are two natural keys:
- Sorted letters:
"eat"→"aet". Building it costs for a word of length . - Count signature: the 26-tuple of letter counts. Building it costs . As a string key, join the counts with a separator (
"1#0#0#0#1#…") so that counts like 1 then 11 cannot be confused with 11 then 1.
Trace on ["eat", "tea", "tan", "ate", "nat", "bat"]:
| Word | Sorted key | Non-zero counts in the count key | Bucket after insertion |
|---|---|---|---|
| eat | aet | a:1, e:1, t:1 | aet → [eat] |
| tea | aet | a:1, e:1, t:1 | aet → [eat, tea] |
| tan | ant | a:1, n:1, t:1 | ant → [tan] |
| ate | aet | a:1, e:1, t:1 | aet → [eat, tea, ate] |
| nat | ant | a:1, n:1, t:1 | ant → [tan, nat] |
| bat | abt | a:1, b:1, t:1 | abt → [bat] |
Result: [[eat, tea, ate], [tan, nat], [bat]].
Palindromes and reversal
Palindrome check: two pointers from the ends move inward, comparing characters. "Valid palindrome" adds filtering: skip non-alphanumerics and compare case-folded. The pointer mechanics and their invariant are covered in Two Pointers.
Reverse words in place (for a mutable character array):
- Reverse the entire array. The words are now in the right order but each is spelled backwards.
- Reverse each word individually.
- Compact: remove leading and trailing spaces and collapse runs of spaces to one, using a write pointer.
All three steps are with extra space. In Python, Java and JavaScript, strings are immutable, so you either convert to a character array (Java toCharArray, Python list(s)) or accept the idiomatic -space " ".join(reversed(s.split())). In C++ the in-place version applies directly to std::string.
Parsing without regex: the atoi state machine
"String to integer" (LeetCode 8) is a specification exercise, and the clean solution is a small deterministic state machine:
- SKIP_WS: skip spaces. On anything else, go to SIGN.
- SIGN: if the character is
+or-, record the sign and consume it. Then go to DIGITS. - DIGITS: while the character is a digit, accumulate. Before accumulating, check for overflow and clamp if needed.
- DONE: any non-digit, or the end of the string, stops parsing. Return
sign * value.
stateDiagram-v2
[*] --> SKIP_WS
SKIP_WS --> SKIP_WS: space
SKIP_WS --> SIGN: other
SIGN --> DIGITS: plus or minus sign, consumed
SIGN --> DIGITS: other, not consumed
DIGITS --> DIGITS: digit, no overflow
DIGITS --> DONE: digit would overflow, clamp
DIGITS --> DONE: non-digit or end
DONE --> [*]
Trace on " -42abc":
| Index | Char | State | Action | Sign | Value |
|---|---|---|---|---|---|
| 0 | ' ' | SKIP_WS | skip | 1 | 0 |
| 1 | ' ' | SKIP_WS | skip | 1 | 0 |
| 2 | '-' | SIGN → DIGITS | set sign | -1 | 0 |
| 3 | '4' | DIGITS | value = value·10 + 4 | -1 | 4 |
| 4 | '2' | DIGITS | value = value·10 + 2 | -1 | 42 |
| 5 | 'a' | DONE | stop | -1 | 42 |
Result: −42.
The overflow check. Accumulate the magnitude as a non-negative number. Before computing value * 10 + d, test value > (INT_MAX - d) / 10 (integer division). If it is true, the next step would exceed , so clamp: return INT_MAX for a positive sign and INT_MIN for a negative one. The same check correctly sends "-2147483648" to INT_MIN. At the last digit, value = 214748364 and d = 8. (2147483647 - 8) / 10 = 214748363 < value, so we clamp to , which is exactly the right answer. The check never computes an out-of-range intermediate, so it is safe in 32-bit arithmetic, and that is what interviewers who say "assume you cannot store 64-bit integers" are probing. The proof is in Correctness.
The same skeleton handles number validation (LeetCode 65), with more states for decimal points and exponents. It also handles tokenizing an expression into numbers, operators and parentheses, which then feeds a stack-based evaluator (Stacks). Writing an explicit state table instead of a regex makes every edge case a visible row you can test.
String building patterns
- Run-length encoding / compression: keep a run start
i, and advancejwhiles[j] == s[i]. Emit the character and the run lengthj - i, then seti = j. "String compression" (LeetCode 443) does this in place on a char array with a separate write pointer. The write pointer never overtakes the read pointer because an encoded run is never longer than the run itself. - Count and say: apply RLE to the previous term, reading each run as "count, digit". The terms go
1,11,21,1211,111221, … - Zigzag conversion: keep one builder per row and a direction that flips at row 0 and row
numRows - 1. Append each character to the current row, then concatenate the rows. The direct-index formula exists, but the simulation is easier to get right.
Case conversion and ASCII arithmetic
In ASCII, 'a'–'z' are 97–122 and 'A'–'Z' are 65–90, so upper and lower case differ by 32 (bit 5). ch - 'a' maps a lowercase letter to 0–25, and 'a' + k maps back: chr(ord('a') + 3) is 'd'. A Caesar shift is (ch - 'a' + k) % 26 + 'a'. Digits '0'–'9' are 48–57, so ch - '0' is the digit's value. These tricks are correct only for ASCII. For general text use the library's isalpha, toLowerCase and Character.isDigit and accept that they are Unicode-aware.
Locale is the trap. In a Turkish locale, uppercase I lowercases to dotless ı (U+0131), and lowercase i uppercases to İ (U+0130). Java's no-argument toLowerCase() uses the default locale, so "TITLE".toLowerCase() on a Turkish-configured server yields "tıtle", and comparisons against "title" fail. This bug has shipped in real software many times. Use toLowerCase(Locale.ROOT) for identifiers and protocol keywords. Case mapping can also change length: "ß".upper() is "SS", and "İ".lower() in Python is i plus U+0307 (2 code points).
Common conversions
| Conversion | Python | Java | C++ | JavaScript |
|---|---|---|---|---|
| int → string | str(n) | Integer.toString(n), String.valueOf(n) | std::to_string(n) | String(n) |
| string → int | int(s) (accepts surrounding spaces) | Integer.parseInt(s) (throws) | std::stoi(s), std::from_chars | Number(s), parseInt(s, 10) |
| char → code | ord(c) | (int) c, s.codePointAt(i) | (unsigned char) c | s.codePointAt(i) |
| code → char | chr(n) | (char) n, Character.toString(cp) | char(n) | String.fromCodePoint(n) |
| string → bytes | s.encode('utf-8') | s.getBytes(StandardCharsets.UTF_8) | already bytes | new TextEncoder().encode(s) |
| bytes → string | b.decode('utf-8') | new String(b, StandardCharsets.UTF_8) | — | new TextDecoder().decode(b) |
Two traps. JavaScript parseInt("08") is 8 today, but always pass the radix. And parseInt stops at the first invalid character while Number rejects the whole string. Java getBytes() without a charset uses the platform default (UTF-8 by default only since JDK 18, JEP 400), so name the charset explicitly.
Hashing strings and matching: previews
Hashing a string costs for its length . That cost is hidden in every "" hash map operation on string keys, which is why anagram grouping is , not . Polynomial rolling hashes extend the idea: the hash of every substring becomes a prefix-hash difference, which enables substring comparison and Rabin–Karp search. That is the same prefix trick as in Prefix Sums, over a group of residues. Rolling hashes get their own lesson in the string-algorithms module. For pattern search, the naive scan is in the worst case. KMP and the Z-algorithm guarantee , and String Algorithms covers them.
The ladder: brute force → better → optimal
Group anagrams
Rung 1: pairwise comparison. For each word, compare it against a representative of every existing group with an anagram test, and add it to the matching group or start a new one. With words of length and groups, this costs , which is when all words are distinct.
Rung 2: sorted key + hash map. Key each word by its sorted letters and bucket. time and space. The improvement replaces "compare against every group" with a hash lookup on a canonical form: equality of keys is equivalence of words, so no pairwise comparison is needed.
Rung 3: count key + hash map. Key each word by its 26-count signature. time, which is for . The improvement removes the factor of sorting. In practice, for short English words (–) the sorted key is often just as fast, because sorting 7 characters is cheap and the count key has a fixed cost of 26. The asymptotic win shows up for long strings. As always, measure (Benchmarks).
Building a string of n pieces
Rung 1: s = s + piece on an immutable string. character copies in total.
Rung 2: builder / join. total. A dynamic buffer with geometric growth gives amortised per append, so the sum of copies is bounded by a constant times the final length.
Rung 3: pre-sized builder. Still , but with reserve or new StringBuilder(capacity) the buffer never reallocates, which removes the constant-factor copying of geometric growth.
Reverse words
Rung 1: split, reverse, join. time, extra space. Idiomatic in Python, Java and JavaScript.
Rung 2: in place on a mutable buffer. time, extra space: reverse all, reverse each word, compact spaces.
| Problem | Approach | Time | Extra space | Note |
|---|---|---|---|---|
| group anagrams | pairwise compare | avoid | ||
| group anagrams | sorted key | simplest; fine for short words | ||
| group anagrams | count key | asymptotically optimal | ||
| valid anagram | sort both | works for any alphabet | ||
| valid anagram | 26-count | lowercase English only | ||
| build string | repeated + | quadratic trap | ||
| build string | builder / join | standard | ||
| reverse words | split + join | idiomatic | ||
| reverse words | in place | needs a mutable buffer |
Correctness
Anagram key uniqueness
Claim: for words over the alphabet , key(u) = key(v) if and only if and are anagrams, for both the sorted key and the count key.
Count key. Two words are anagrams exactly when every letter occurs the same number of times in both, which is the definition of having the same multiset. The count vector records exactly the multiplicity of each letter, so equal vectors mean equal multisets and vice versa. To serialise the vector into a string, use a separator between counts (or fixed-width fields). Without one, the vectors and both serialise to "111", and the map would be injective on vectors but not on strings.
Sorted key. Sorting is a function of the multiset alone, since any permutation of the input sorts to the same output. Conversely, a sorted string lists each letter exactly as many times as it occurs, so it determines the multiset. Equal sorted strings therefore mean equal multisets.
Because the key is a complete invariant of the equivalence relation "is an anagram of", grouping by key produces exactly the equivalence classes. No two anagrams are separated and no two non-anagrams are merged.
atoi overflow check
Claim: for and a digit , if and only if , where .
() gives , so . Since is an integer, . () , so and .
So the test v > (M - d) / 10 (integer division, with non-negative operands so truncation equals floor) fires exactly when the next accumulated magnitude would exceed . The algorithm stores only magnitudes , so no intermediate ever overflows 32-bit arithmetic.
Negative results need the magnitude , which does not fit. If the next magnitude would be , the check fires and we return . That is correct for exactly and is the required clamp for anything larger. If the magnitude stays , the result is in range. Every input therefore yields the specified clamped value.
In-place word reversal
Let the words be separated by spaces. Reversing the whole buffer produces with the spaces mirrored, because reversing a concatenation reverses the order of the parts and reverses each part: . Reversing each maximal non-space run then turns each back into , leaving . Compaction only deletes spaces and keeps the order of non-space characters, so the words stay intact and in reversed order.
Complexity
| Operation | Python | Java | C++ std::string | JavaScript |
|---|---|---|---|---|
| length | code points | code units | bytes | code units |
index s[i] | (PEP 393 fixed width) | unit | byte | unit, may flatten a rope first |
| -th code point | scan (offsetByCodePoints) | scan of UTF-8 | scan | |
| substring of length | copy | copy | substr , string_view | engine-dependent |
| concatenate | same | += amortised | often via rope | |
| equality | worst, early exit | |||
| hash | first time, cached | first time, cached | every time | engine caches |
For the problem families on this page:
- Frequency counting is time with space.
- Group anagrams is with count keys.
- atoi is time and space.
- Reverse words is .
- RLE is .
- Count-and-say for term is . The term lengths grow by a factor approaching Conway's constant ≈ 1.3036 per step.
Constants matter. A 26-entry int array is 104 bytes and lives in L1 cache, while a hash map allocates per key and chases pointers. For short ASCII strings the count array is typically several times faster than Counter or HashMap<Character, Integer>, which also boxes every char in Java. These ratios are indicative; measure on your workload.
Implementation
Four routines per language: valid anagram with a 26-count, group anagrams by count key, atoi with an overflow clamp, and reverse words. Python, Java and TypeScript reverse words by splitting. C++ reverses in place because std::string is mutable. The test data is identical across languages.
INT_MAX, INT_MIN = 2**31 - 1, -(2**31)
def is_anagram(s: str, t: str) -> bool:
"""Lowercase English letters only."""
if len(s) != len(t):
return False
counts = [0] * 26
for a, b in zip(s, t):
counts[ord(a) - 97] += 1
counts[ord(b) - 97] -= 1
return all(c == 0 for c in counts)
def group_anagrams(words: list[str]) -> list[list[str]]:
groups: dict[tuple[int, ...], list[str]] = {}
for w in words:
counts = [0] * 26
for ch in w:
counts[ord(ch) - 97] += 1
groups.setdefault(tuple(counts), []).append(w) # tuple = unambiguous key
return list(groups.values())
def my_atoi(s: str) -> int:
i, n = 0, len(s)
while i < n and s[i] == " ": # SKIP_WS
i += 1
sign = 1
if i < n and s[i] in "+-": # SIGN
sign = -1 if s[i] == "-" else 1
i += 1
value = 0
while i < n and "0" <= s[i] <= "9": # DIGITS
d = ord(s[i]) - 48
if value > (INT_MAX - d) // 10: # next step would exceed INT_MAX
return INT_MAX if sign == 1 else INT_MIN
value = value * 10 + d
i += 1
return sign * value # DONE
def reverse_words(s: str) -> str:
return " ".join(reversed(s.split())) # split() drops empty pieces
def normalise(groups: list[list[str]]) -> list[list[str]]:
return sorted(sorted(g) for g in groups)
if __name__ == "__main__":
assert is_anagram("anagram", "nagaram")
assert not is_anagram("rat", "car")
assert not is_anagram("a", "ab")
got = normalise(group_anagrams(["eat", "tea", "tan", "ate", "nat", "bat"]))
assert got == [["ate", "eat", "tea"], ["bat"], ["nat", "tan"]]
assert normalise(group_anagrams([""])) == [[""]]
cases = {"42": 42, " -42abc": -42, "4193 with words": 4193, "words 987": 0,
"-91283472332": INT_MIN, "2147483648": INT_MAX, "2147483647": INT_MAX,
"-2147483648": INT_MIN, "+-12": 0, "": 0, " +0 123": 0}
for text, want in cases.items():
assert my_atoi(text) == want, (text, my_atoi(text), want)
assert reverse_words(" the sky is blue ") == "blue is sky the"
assert reverse_words("a") == "a"
print("strings: all tests passed")
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
public class StringsInDepth {
/** Lowercase English letters only. */
static boolean isAnagram(String s, String t) {
if (s.length() != t.length()) return false;
int[] counts = new int[26];
for (int i = 0; i < s.length(); i++) {
counts[s.charAt(i) - 'a']++;
counts[t.charAt(i) - 'a']--;
}
for (int c : counts) if (c != 0) return false;
return true;
}
static List<List<String>> groupAnagrams(String[] words) {
Map<String, List<String>> groups = new HashMap<>();
for (String w : words) {
int[] counts = new int[26];
for (int i = 0; i < w.length(); i++) counts[w.charAt(i) - 'a']++;
String key = Arrays.toString(counts); // "[1, 0, ...]" - separators make it unambiguous
groups.computeIfAbsent(key, k -> new ArrayList<>()).add(w);
}
return new ArrayList<>(groups.values());
}
static int myAtoi(String s) {
int i = 0, n = s.length();
while (i < n && s.charAt(i) == ' ') i++; // SKIP_WS
int sign = 1;
if (i < n && (s.charAt(i) == '+' || s.charAt(i) == '-')) { // SIGN
sign = s.charAt(i) == '-' ? -1 : 1;
i++;
}
int value = 0; // magnitude, never exceeds INT_MAX
while (i < n && s.charAt(i) >= '0' && s.charAt(i) <= '9') { // DIGITS
int d = s.charAt(i) - '0';
if (value > (Integer.MAX_VALUE - d) / 10) {
return sign == 1 ? Integer.MAX_VALUE : Integer.MIN_VALUE;
}
value = value * 10 + d;
i++;
}
return sign * value; // DONE
}
static String reverseWords(String s) {
String[] parts = s.trim().split("\\s+");
Collections.reverse(Arrays.asList(parts));
return String.join(" ", parts);
}
static List<List<String>> normalise(List<List<String>> groups) {
List<List<String>> out = new ArrayList<>();
for (List<String> g : groups) {
List<String> copy = new ArrayList<>(g);
Collections.sort(copy);
out.add(copy);
}
out.sort((a, b) -> a.get(0).compareTo(b.get(0)));
return out;
}
static void check(boolean ok, String what) {
if (!ok) throw new AssertionError(what);
}
public static void main(String[] args) {
check(isAnagram("anagram", "nagaram"), "anagram true");
check(!isAnagram("rat", "car"), "anagram false");
check(!isAnagram("a", "ab"), "anagram length");
List<List<String>> got = normalise(groupAnagrams(new String[]{"eat", "tea", "tan", "ate", "nat", "bat"}));
check(got.equals(List.of(List.of("ate", "eat", "tea"), List.of("bat"), List.of("nat", "tan"))), "group anagrams " + got);
String[] inputs = {"42", " -42abc", "4193 with words", "words 987", "-91283472332",
"2147483648", "2147483647", "-2147483648", "+-12", "", " +0 123"};
int[] expected = {42, -42, 4193, 0, Integer.MIN_VALUE, Integer.MAX_VALUE, Integer.MAX_VALUE,
Integer.MIN_VALUE, 0, 0, 0};
for (int k = 0; k < inputs.length; k++) {
check(myAtoi(inputs[k]) == expected[k], "atoi " + inputs[k]);
}
check(reverseWords(" the sky is blue ").equals("blue is sky the"), "reverse words");
check(reverseWords("a").equals("a"), "reverse single");
System.out.println("strings: all tests passed");
}
}
#include <algorithm>
#include <array>
#include <cassert>
#include <climits>
#include <iostream>
#include <map>
#include <string>
#include <vector>
using std::string;
using std::vector;
// Lowercase English letters only.
bool isAnagram(const string& s, const string& t) {
if (s.size() != t.size()) return false;
std::array<int, 26> counts{};
for (std::size_t i = 0; i < s.size(); ++i) {
++counts[s[i] - 'a'];
--counts[t[i] - 'a'];
}
return std::all_of(counts.begin(), counts.end(), [](int c) { return c == 0; });
}
vector<vector<string>> groupAnagrams(const vector<string>& words) {
std::map<std::array<int, 26>, vector<string>> groups; // array compares element-wise: unambiguous
for (const string& w : words) {
std::array<int, 26> counts{};
for (char ch : w) ++counts[ch - 'a'];
groups[counts].push_back(w);
}
vector<vector<string>> out;
for (auto& [key, g] : groups) out.push_back(g);
return out;
}
int myAtoi(const string& s) {
std::size_t i = 0, n = s.size();
while (i < n && s[i] == ' ') ++i; // SKIP_WS
int sign = 1;
if (i < n && (s[i] == '+' || s[i] == '-')) { // SIGN
sign = s[i] == '-' ? -1 : 1;
++i;
}
int value = 0; // magnitude, never exceeds INT_MAX
while (i < n && s[i] >= '0' && s[i] <= '9') { // DIGITS
int d = s[i] - '0';
if (value > (INT_MAX - d) / 10) return sign == 1 ? INT_MAX : INT_MIN;
value = value * 10 + d;
++i;
}
return sign * value; // DONE
}
// In place: reverse all, reverse each word, compact spaces.
void reverseWords(string& s) {
std::reverse(s.begin(), s.end());
std::size_t write = 0, n = s.size(), i = 0;
while (i < n) {
if (s[i] == ' ') { ++i; continue; }
if (write > 0) s[write++] = ' '; // single separator
std::size_t start = write;
while (i < n && s[i] != ' ') s[write++] = s[i++]; // copy word (write <= i always)
std::reverse(s.begin() + start, s.begin() + write);
}
s.resize(write);
}
vector<vector<string>> normalise(vector<vector<string>> groups) {
for (auto& g : groups) std::sort(g.begin(), g.end());
std::sort(groups.begin(), groups.end());
return groups;
}
int main() {
assert(isAnagram("anagram", "nagaram"));
assert(!isAnagram("rat", "car"));
assert(!isAnagram("a", "ab"));
auto got = normalise(groupAnagrams({"eat", "tea", "tan", "ate", "nat", "bat"}));
assert((got == vector<vector<string>>{{"ate", "eat", "tea"}, {"bat"}, {"nat", "tan"}}));
vector<std::pair<string, int>> cases = {
{"42", 42}, {" -42abc", -42}, {"4193 with words", 4193}, {"words 987", 0},
{"-91283472332", INT_MIN}, {"2147483648", INT_MAX}, {"2147483647", INT_MAX},
{"-2147483648", INT_MIN}, {"+-12", 0}, {"", 0}, {" +0 123", 0}};
for (const auto& [text, want] : cases) assert(myAtoi(text) == want);
string a = " the sky is blue ";
reverseWords(a);
assert(a == "blue is sky the");
string b = "a";
reverseWords(b);
assert(b == "a");
std::cout << "strings: all tests passed\n";
return 0;
}
const INT_MAX = 2 ** 31 - 1;
const INT_MIN = -(2 ** 31);
// Lowercase English letters only.
function isAnagram(s: string, t: string): boolean {
if (s.length !== t.length) return false;
const counts = new Array<number>(26).fill(0);
for (let i = 0; i < s.length; i++) {
counts[s.charCodeAt(i) - 97]++;
counts[t.charCodeAt(i) - 97]--;
}
return counts.every(c => c === 0);
}
function groupAnagrams(words: string[]): string[][] {
const groups = new Map<string, string[]>();
for (const w of words) {
const counts = new Array<number>(26).fill(0);
for (let i = 0; i < w.length; i++) counts[w.charCodeAt(i) - 97]++;
const key = counts.join("#"); // separator makes the key unambiguous
const g = groups.get(key);
if (g) g.push(w); else groups.set(key, [w]);
}
return [...groups.values()];
}
function myAtoi(s: string): number {
let i = 0;
const n = s.length;
while (i < n && s[i] === " ") i++; // SKIP_WS
let sign = 1;
if (i < n && (s[i] === "+" || s[i] === "-")) { // SIGN
sign = s[i] === "-" ? -1 : 1;
i++;
}
let value = 0;
while (i < n && s[i] >= "0" && s[i] <= "9") { // DIGITS
const d = s.charCodeAt(i) - 48;
if (value > Math.floor((INT_MAX - d) / 10)) return sign === 1 ? INT_MAX : INT_MIN;
value = value * 10 + d;
i++;
}
return sign * value || 0; // DONE ("|| 0" turns -0 into 0)
}
function reverseWords(s: string): string {
return s.trim().split(/\s+/).reverse().join(" ");
}
function normalise(groups: string[][]): string[][] {
return groups.map(g => [...g].sort()).sort((a, b) => (a[0] < b[0] ? -1 : a[0] > b[0] ? 1 : 0));
}
function check(ok: boolean, what: string): void {
if (!ok) throw new Error("FAILED: " + what);
}
check(isAnagram("anagram", "nagaram"), "anagram true");
check(!isAnagram("rat", "car"), "anagram false");
check(!isAnagram("a", "ab"), "anagram length");
const got = normalise(groupAnagrams(["eat", "tea", "tan", "ate", "nat", "bat"]));
check(JSON.stringify(got) === JSON.stringify([["ate", "eat", "tea"], ["bat"], ["nat", "tan"]]), "group anagrams");
const cases: [string, number][] = [
["42", 42], [" -42abc", -42], ["4193 with words", 4193], ["words 987", 0],
["-91283472332", INT_MIN], ["2147483648", INT_MAX], ["2147483647", INT_MAX],
["-2147483648", INT_MIN], ["+-12", 0], ["", 0], [" +0 123", 0],
];
for (const [text, want] of cases) check(myAtoi(text) === want, "atoi " + JSON.stringify(text));
check(reverseWords(" the sky is blue ") === "blue is sky the", "reverse words");
check(reverseWords("a") === "a", "reverse single");
console.log("strings: all tests passed");
Unicode handling, side by side
The same string, "😀a", measured in each language: 2 code points, 3 UTF-16 code units, 5 UTF-8 bytes. Each block counts code points the idiomatic way and asserts the numbers.
import unicodedata
s = "\U0001F600a" # 😀a
assert len(s) == 2 # code points
assert len(s.encode("utf-8")) == 5 # UTF-8 bytes
assert len(s.encode("utf-16-le")) // 2 == 3 # UTF-16 code units
assert "\U0001F600".encode("utf-8") == b"\xf0\x9f\x98\x80"
nfc = "é" # é precomposed
nfd = unicodedata.normalize("NFD", nfc) # e + combining acute
assert (len(nfc), len(nfd)) == (1, 2) and nfc != nfd
assert unicodedata.normalize("NFC", nfd) == nfc
print("python unicode ok")
import java.nio.charset.StandardCharsets;
import java.text.Normalizer;
public class UnicodeCounts {
static void check(boolean ok, String what) {
if (!ok) throw new AssertionError(what);
}
public static void main(String[] args) {
String s = "😀a"; // 😀a as a surrogate pair + 'a'
check(s.length() == 3, "length counts UTF-16 units");
check(s.codePointCount(0, s.length()) == 2, "code points");
check(s.codePoints().count() == 2, "codePoints stream");
check(s.getBytes(StandardCharsets.UTF_8).length == 5, "UTF-8 bytes");
check(Character.isHighSurrogate(s.charAt(0)), "charAt(0) is half a character");
check(s.codePointAt(0) == 0x1F600, "codePointAt reads the whole code point");
String nfc = "é";
String nfd = Normalizer.normalize(nfc, Normalizer.Form.NFD);
check(nfc.length() == 1 && nfd.length() == 2 && !nfc.equals(nfd), "NFC vs NFD");
check(Normalizer.normalize(nfd, Normalizer.Form.NFC).equals(nfc), "round trip");
System.out.println("java unicode ok");
}
}
#include <cassert>
#include <cstddef>
#include <iostream>
#include <string>
// Count code points in a UTF-8 string: count bytes that are NOT continuation bytes (10xxxxxx).
std::size_t utf8CodePoints(const std::string& s) {
std::size_t n = 0;
for (unsigned char b : s) {
if ((b & 0xC0) != 0x80) ++n;
}
return n;
}
int main() {
std::string s = "\xF0\x9F\x98\x80" "a"; // 😀a encoded as UTF-8 bytes
assert(s.size() == 5); // size() counts bytes
assert(utf8CodePoints(s) == 2);
std::u16string u = u"\U0001F600a";
assert(u.size() == 3); // UTF-16 code units
std::u32string w = U"\U0001F600a";
assert(w.size() == 2); // UTF-32: one unit per code point
std::cout << "c++ unicode ok\n";
return 0;
}
const s = "\u{1F600}a"; // 😀a
if (s.length !== 3) throw new Error("length counts UTF-16 units");
if ([...s].length !== 2) throw new Error("spread iterates code points");
if (Array.from(s).length !== 2) throw new Error("Array.from iterates code points");
if (new TextEncoder().encode(s).length !== 5) throw new Error("UTF-8 bytes");
if (s.charCodeAt(0) !== 0xd83d || s.charCodeAt(1) !== 0xde00) throw new Error("surrogate pair");
if (s.codePointAt(0) !== 0x1f600) throw new Error("codePointAt");
const nfc = "é";
const nfd = nfc.normalize("NFD");
if (nfc.length !== 1 || nfd.length !== 2 || nfc === nfd) throw new Error("NFC vs NFD");
if (nfd.normalize("NFC") !== nfc) throw new Error("round trip");
console.log("typescript unicode ok");
C++ has no normalization in the standard library. Use ICU (icu::Normalizer2) when you need it.
Real-world uses
Text processing pipelines. Search engines, log processors and data pipelines start with the steps on this page: decode bytes to text (choosing an encoding and handling invalid sequences), normalize (NFC or NFKC), case-fold, then split into tokens. Getting the first step wrong produces mojibake: é instead of é is UTF-8 bytes decoded as Latin-1. Indexing for search is covered in Search Engineering.
Tokenizers. Compilers tokenize source code with exactly the state-machine approach of atoi, usually generated from a regular grammar. LLM tokenizers (byte-pair encoding) start from UTF-8 bytes precisely so that every possible string is representable, then merge frequent byte pairs. That is why a single emoji can cost several tokens.
URL parsing. A URL is parsed by a state machine (the WHATWG URL Standard specifies it state by state), with percent-encoding of UTF-8 bytes for non-ASCII characters. é in a path becomes %C3%A9: its two UTF-8 bytes, each written as %XX. Internationalised domain names are converted to ASCII with Punycode (xn--…) before DNS sees them.
DNS labels. DNS names are sequences of labels of at most 63 octets each, with a total wire length of at most 255 octets. Comparison is ASCII case-insensitive (RFC 4343). Unicode names reach DNS only through the IDNA/Punycode conversion. See DNS Deep Dive.
Log parsing. Splitting a log line on spaces breaks on quoted fields. Production parsers (for example, those for the nginx combined log format) are hand-written tokenizers or anchored regexes, and the fast ones avoid allocating substrings by returning index ranges into the line. That is the string_view idea.
Database collation. ORDER BY name and WHERE name = 'x' depend on the column's collation, which decides whether é = e, whether comparison is case-sensitive, and how trailing spaces are treated. A unique index under a case-insensitive collation rejects Alice when alice exists. Changing a collation can silently corrupt an index if the sort order it was built with no longer matches. See SQL Fundamentals.
Hash maps keyed by strings. Every language runtime caches string hashes or interns strings to make symbol tables, JSON object keys and HTTP header maps fast. Java's switch on strings compiles to a hashCode switch followed by equals.
Pitfalls & edge cases
length is not the character count. It counts code points in Python, UTF-16 code units in Java and JavaScript, and bytes in C++. Truncating a user's name to "20 characters" with substring(0, 20) can cut a surrogate pair in half and produce invalid UTF-16. Truncate on code point or grapheme boundaries.
charAt on surrogates. In Java and JavaScript, charAt(i) on an emoji returns half a character. Reversing a string by reversing its chars swaps the surrogate halves and corrupts every astral character. Reverse by code point ([...s].reverse().join('') in JS, new StringBuilder(s).reverse() in Java, which handles surrogate pairs). Even code-point reversal breaks combining marks and ZWJ sequences.
== on Java strings. It compares references. It works for literals by accident of interning and fails for strings built at runtime. Use equals, or Objects.equals if either side can be null.
Mutating while iterating. In C++, appending to a std::string while holding iterators or a string_view into it invalidates them on reallocation. In any language, building a new string while reading the old one is the safe pattern.
Locale-dependent case conversion. The Turkish i problem. Use Locale.ROOT in Java, casefold() in Python, and toLowerCase() (not toLocaleLowerCase()) in JavaScript for identifiers.
Concatenation in loops. on immutable strings. Use a builder. The C++ version of the bug is s = s + x.
substring memory in old Java. Before JDK 7u6, a small substring kept its huge parent char[] alive. This is fixed today, but the same pattern exists with V8 sliced strings and with C++ string_view (dangling rather than leaking).
Null vs empty. In Java, null and "" are different, and s.isEmpty() throws on null. A method that accepts both should say what it returns for each. In Python, None vs "". In databases, Oracle treats '' as NULL, a famous portability trap.
Splitting and trailing spaces. Python "a b ".split(" ") gives ['a', '', 'b', ''], while split() with no argument gives ['a', 'b']. Java "a b ".split(" ") gives [a, , b]: it keeps interior empties but drops trailing ones. JavaScript "a b ".split(" ") keeps all of them. Always say which you want, and prefer splitting on \s+ after trimming.
ch - 'a' on non-lowercase input. It produces negative or out-of-range indices, which in C++ and Java means out-of-bounds access. Validate or use a map.
Overflow when parsing. value * 10 + d in 32-bit arithmetic wraps silently in C++ (undefined behaviour for signed integers) and Java. Check before multiplying.
Comparing unnormalized text. "é" == "é" can be false. Normalize at input boundaries.
Variations
Byte strings. Python bytes/bytearray, Java byte[], C++ std::string used as a byte buffer, JavaScript Uint8Array. Use them for binary data, network protocols and anything where "character" has no meaning. All the frequency and parsing techniques apply with a 256-entry count array.
Ropes. A binary tree whose leaves are string chunks. Concatenation and splitting are , and indexing is . Text editors (Xi, and the piece-table cousin in VS Code) and JavaScript engines (cons strings) use them for large, frequently edited text.
Builders with capacity. StringBuilder(int capacity), std::string::reserve, and pre-sized bytearray. Same asymptotics as a plain builder, fewer reallocations, and a measurable difference in tight loops.
Tries. A tree keyed by characters. Prefix lookup and autocomplete cost for a key of length , independent of how many strings are stored. Covered with the tree structures in Advanced Data Structures.
Suffix structures. Suffix arrays, suffix automata and suffix trees answer "does pattern occur in , and where" in time proportional to after preprocessing . They have their own lessons in the string-algorithms module, Module 7.
Rolling hashes. Prefix hashes over a modular group give substring equality checks (with a tiny false-positive probability) and power Rabin–Karp search. They also have their own lesson in Module 7. Bit Manipulation covers the related trick of packing a 26-bit parity mask per prefix.
Grapheme-aware processing. For user-facing truncation, cursor movement and "reverse the visible characters", segment text by grapheme cluster (Unicode UAX #29) with Intl.Segmenter in JavaScript, ICU's BreakIterator in Java and C++, or the third-party regex module's \X in Python.
Practice ladder
Each problem is described in my own words; follow the link for the formal statement.
1. Valid Anagram (LeetCode 242): decide whether two lowercase strings use the same letters with the same multiplicities. Teaches the 26-count array.
Hint
Increment for one string, decrement for the other, check all zeros. The follow-up asks about Unicode input: switch to a hash map.
2. First Unique Character in a String (LeetCode 387): find the index of the first character that occurs exactly once. Teaches the count-then-scan two-pass pattern.
Hint
Count every character in pass 1. In pass 2 return the first index whose count is 1.
3. Valid Palindrome (LeetCode 125): palindrome check that ignores case and non-alphanumeric characters. Teaches two pointers with filtering and no extra string.
Hint
Move i forward and j backward past non-alphanumerics, then compare lowercase versions. Avoid building a filtered copy if asked for space.
Solution
def is_palindrome(s: str) -> bool:
i, j = 0, len(s) - 1
while i < j:
while i < j and not s[i].isalnum():
i += 1
while i < j and not s[j].isalnum():
j -= 1
if s[i].lower() != s[j].lower():
return False
i += 1
j -= 1
return True
assert is_palindrome("A man, a plan, a canal: Panama")
assert not is_palindrome("race a car")
assert is_palindrome(" ")
print("125 ok")
time, extra space. The inner loops keep i < j, so the pointers never cross while skipping.
4. Group Anagrams (LeetCode 49): bucket words that are anagrams of each other. Teaches canonical keys and the sorted-vs-count trade-off. The canonical implementation above is a complete solution.
Hint
Key each word by its sorted letters or by its 26-count tuple, and append the word to groups[key].
5. Sherlock and Anagrams (HackerRank): count pairs of substrings of one string that are anagrams of each other. Teaches canonical keys applied to all substrings and pair counting.
Hint
For every substring compute its sorted (or count) key and tally the keys. Each key seen times contributes pairs.
6. Reverse Words in a String (LeetCode 151): reverse the order of words, normalising spaces. Teaches split-and-join and the in-place reverse-all, reverse-each, compact method.
Hint
Idiomatic: split on whitespace, reverse, join with single spaces. Follow-up ( space on a mutable buffer): see the C++ implementation above.
7. Find the Index of the First Occurrence in a String (LeetCode 28): find a needle in a haystack. Teaches the naive scan and motivates KMP.
Hint
Try every start position and compare up to len(needle) characters. Then read about KMP's failure function in String Algorithms for the guarantee.
8. Zigzag Conversion (LeetCode 6): write a string in a zigzag over numRows rows and read it row by row. Teaches simulation with one builder per row.
Hint
Keep a current row and a direction. Flip the direction at the top and bottom rows. Handle numRows == 1 separately.
Solution
def convert(s: str, num_rows: int) -> str:
if num_rows == 1 or num_rows >= len(s):
return s
rows = [[] for _ in range(num_rows)]
r, step = 0, 1
for ch in s:
rows[r].append(ch)
if r == 0:
step = 1
elif r == num_rows - 1:
step = -1
r += step
return "".join("".join(row) for row in rows)
assert convert("PAYPALISHIRING", 3) == "PAHNAPLSIIGYIR"
assert convert("PAYPALISHIRING", 4) == "PINALSIGYAHRPI"
assert convert("A", 1) == "A"
print("6 ok")
time and space. Each character is appended once, and the final join is linear because it uses list builders, not repeated concatenation.
9. Count and Say (LeetCode 38): produce the -th term of the look-and-say sequence. Teaches run-length encoding with a builder.
Hint
Each term is the RLE of the previous one, written as count then digit. Use ''.join on a list of pieces.
Solution
def count_and_say(n: int) -> str:
term = "1"
for _ in range(n - 1):
pieces = []
i = 0
while i < len(term):
j = i
while j < len(term) and term[j] == term[i]:
j += 1
pieces.append(str(j - i))
pieces.append(term[i])
i = j
term = "".join(pieces)
return term
assert [count_and_say(k) for k in range(1, 6)] == ["1", "11", "21", "1211", "111221"]
print("38 ok")
Each step is linear in the current term's length, so the total cost is the sum of all term lengths. Those lengths grow by a factor tending to Conway's constant, about 1.3036, per step.
10. String Compression (LeetCode 443): run-length encode a char array in place and return the new length. Teaches read and write pointers and why the write pointer never overtakes the read pointer.
Hint
For each run of length , write the character, then the digits of if . The encoding of a run is never longer than the run, so writing in place is safe.
Solution
def compress(chars: list[str]) -> int:
write = read = 0
while read < len(chars):
ch = chars[read]
start = read
while read < len(chars) and chars[read] == ch:
read += 1
chars[write] = ch
write += 1
run = read - start
if run > 1:
for digit in str(run):
chars[write] = digit
write += 1
return write
a = list("aabbccc")
assert compress(a) == 6 and a[:6] == list("a2b2c3")
b = list("abbbbbbbbbbbb")
assert compress(b) == 4 and b[:4] == list("ab12")
c = ["a"]
assert compress(c) == 1
print("443 ok")
time, extra space. For a run of length the encoding uses cells, so write stays at or behind read.
11. String to Integer (atoi) (LeetCode 8): parse a leading integer with whitespace, sign and clamping. Teaches the state machine and the pre-multiplication overflow check. The canonical implementation above is a complete solution.
Hint
States: skip spaces, optional sign, digits. Before value = value * 10 + d, check value > (INT_MAX - d) // 10.
12. Encode and Decode Strings (LeetCode 271): serialise a list of arbitrary strings into one string and back. Teaches length-prefix framing, the same technique network protocols use. (Premium on LeetCode; the idea is what matters.)
Hint
Write each string as len#content. The decoder reads digits up to #, then exactly len characters. Delimiter escaping is the fragile alternative.
Solution
def encode(strs: list[str]) -> str:
return "".join(f"{len(s)}#{s}" for s in strs)
def decode(data: str) -> list[str]:
out, i = [], 0
while i < len(data):
j = data.index("#", i)
length = int(data[i:j])
out.append(data[j + 1 : j + 1 + length])
i = j + 1 + length
return out
for case in (["lint", "code", "love", "you"], ["", "#", "3#abc", "a#b"], []):
assert decode(encode(case)) == case
print("271 ok")
for both directions. Content can contain # or digits freely because the length prefix tells the decoder exactly where each string ends.
13. Decode String (LeetCode 394): expand nested patterns like 3[a2[c]]. A preview of the next lesson: tokenizing plus a stack of (count, partial builder).
Hint
On [ push the current count and builder and start fresh. On ] pop and append the inner builder count times to the outer one. Accumulate multi-digit counts. See Stacks.
14. Valid Number (LeetCode 65): decide whether a string is a valid decimal or scientific-notation number. Teaches an explicit state table with many states and exhaustive edge cases.
Hint
Track three flags (seen digit, seen dot, seen exponent) and reset "seen digit" after e. A sign is legal only at the start or right after e. Writing the full state table is the most robust approach.
15. Text Justification (LeetCode 68): lay out words into fully justified lines of fixed width. Teaches greedy line filling plus careful space distribution: extra spaces go to the leftmost gaps, and the last line is left-justified.
Hint
Greedily take as many words as fit (with single spaces). Then distribute width - letters spaces across gaps: each gap gets spaces // gaps and the first spaces % gaps gaps get one more. Single-word lines and the last line are left-justified and padded on the right.
Common mistakes & interview follow-ups
"What if the input contains Unicode, not just lowercase letters?" Replace the 26-array with a hash map keyed by code point. In Java and JavaScript, iterate by code point (codePoints(), for...of), not by charAt. Mention normalization: decide whether é precomposed and decomposed count as the same character, and normalize to NFC first if so.
"What is the time complexity of your hash map solution, really?" Hashing a string key of length costs , so "group anagrams in " is really . Java and Python cache string hashes, which helps only for repeated lookups of the same string object.
"Your solution builds strings in a loop. What is its complexity?" On immutable strings each += copies, so the total is . Switch to a builder. In JavaScript, mention that engines use ropes, but do not rely on it in an interview answer.
"The input is a 10 GB log file. Count word frequencies." Stream it: read in chunks, decode incrementally (a multi-byte UTF-8 sequence can straddle a chunk boundary, so use an incremental decoder), and tokenize per chunk while carrying the partial last token to the next chunk. Keep counts in a hash map. If the map does not fit in memory, use a count-min sketch for approximate heavy hitters (Probabilistic Data Structures) or shard by hash to disk.
"atoi without 64-bit integers?" That is exactly what the pre-multiplication check does. Explain why value * 10 + d > INT_MAX is the wrong test (it overflows before the comparison) and why value > (INT_MAX - d) / 10 is equivalent and safe.
"Reverse a string that contains emoji." Reverse by code point, and mention that combining marks and ZWJ sequences need grapheme segmentation to survive.
"Compare two version strings like 1.10 and 1.9." Split on ., compare numerically per component, and treat missing components as 0. Lexicographic comparison is wrong ("1.10" < "1.9").
"Is s1 == s2 correct here?" In Java, no. Use equals. In Python, == is value equality and is is identity. In C, == on char* compares pointers. Use strcmp.
"Case-insensitive comparison?" casefold in Python, equalsIgnoreCase or toLowerCase(Locale.ROOT) in Java, localeCompare with sensitivity: 'base' in JavaScript for human text. Mention the Turkish i.
Common mistakes interviewers watch for: ch - 'a' on input that is not guaranteed lowercase; quadratic concatenation; == on Java strings; forgetting the overflow check; Python s.split(" ") producing empty strings; substring slicing inside recursion causing hidden .
Quick quiz
1. What do len / length / size() return for "😀a" in Python, Java, JavaScript and C++ (UTF-8 std::string)?
Answer
Python 2 (code points), Java 3 and JavaScript 3 (UTF-16 code units: a surrogate pair plus a), C++ 5 (UTF-8 bytes: 4 for the emoji plus 1).
2. Encode U+00E9 (é) in UTF-8 by hand.
Answer
0xE9 = 00011 101001 in 11 bits. That gives 110 00011 = 0xC3 and 10 101001 = 0xA9, so the encoding is C3 A9.
3. Why is s += c inside a loop in Java but usually fine with std::string in C++?
Answer
Java strings are immutable, so each += allocates a new string and copies all existing characters. That totals . std::string is mutable, and += appends into a geometrically growing buffer: amortised per character, total.
4. Why must a count-based anagram key include separators when serialised as a string?
Answer
Without separators, different count vectors can serialise identically: counts (1, 11) and (11, 1) both become "111". Separators (or fixed-width fields, or using a tuple directly as the key) make the serialisation injective, so equal keys imply equal multisets.
5. In atoi, why is value > (INT_MAX - d) / 10 the right overflow test rather than value * 10 + d > INT_MAX?
Answer
The second form computes value * 10 + d first, which itself overflows (wraps or is undefined behaviour) exactly in the case you are trying to detect. The first form uses only in-range arithmetic, and for non-negative integers it is equivalent: .
Further reading / sources
- The Unicode Standard, chapter 3 "Conformance" (UTF-8/16/32 definitions) and UAX #15 Unicode Normalization Forms, UAX #29 Text Segmentation, UTS #10 Unicode Collation Algorithm.
- RFC 3629, UTF-8, a transformation format of ISO 10646 (2003). It restricts UTF-8 to 4 bytes and U+10FFFF.
- Rob Pike, "UTF-8 history", the account of the 1992 design.
- PEP 393: Flexible String Representation (Python 3.3).
- JEP 254: Compact Strings (JDK 9) and JEP 400: UTF-8 by Default (JDK 18).
- Joel Spolsky, "The Absolute Minimum Every Software Developer Absolutely, Positively Must Know About Unicode and Character Sets" (2003). Dated, but still the best short motivation.
- Sedgewick and Wayne, Algorithms, 4th ed., chapter 5 "Strings": string sorts, tries, substring search.
- cp-algorithms: String hashing and Prefix function (KMP).
Previous lesson: Matrices & 2D Grids · Next lesson: Stacks
Related: Module 1 overview · Arrays & Strings · Two Pointers · Sliding Window · Hash Tables · String Algorithms · Regex Mastery · Your Language's Data Structures · How Data Structures Live in Memory · Course home