String manipulation

coreCommon atGoogleMetaAmazonStripeOpenAIRead firstArraysPractise in the Sandbox →

A string is an array of characters you can’t modify: every “change” makes a new string, so building one with += in a loop can cost O(n²). Collect pieces and join once (or use a builder) for O(n). Characters are numbers underneath, so ch - 'a' style arithmetic gives you O(1) letter indexes, as long as you know which “character” your language counts.

The idea in plain words

Strings in Python, JavaScript and C# are immutable: once created, their contents never change. That’s what makes them safe to share, use as hash keys, and pass around without defensive copies.

The consequence: s = s + "x" doesn’t extend s. It allocates a new string of length len(s) + 1, copies all of s into it, then adds "x". Do that n times and you copy 1 + 2 + … + n ≈ n²/2 characters.

The fix in every language is the same idea as a dynamic array: keep a growable buffer of pieces and turn it into one string at the end.

• Python: parts.append(piece) then "".join(parts) (or io.StringIO).
• TypeScript: parts.push(piece) then parts.join("").
• C#: StringBuilder.Append(piece) then .ToString(), or string.Join / string.Concat.

See it

Append words both ways and compare how many characters get copied. The += lane recopies the whole string every time; the builder lane only writes the new piece, plus an occasional doubling.

Building a string: += vs a builder

sandbox

append a wordappend ×10append ×50reset

s = s + piece (immutable): every append builds a brand-new string. Yellow = characters copied by the last append.

builder / list + join: append writes into spare capacity (dashed). Green = characters written by the last append. capacity = 8

+= : chars copied

0

builder: chars copied

0

After 0 appends the string has 0 chars. Repeated += copies about n²/(2·piece) characters; the builder copies about 2n(amortized doubling) plus one final ToString() / join (included in the green bar). Press ×50 a few times and watch the gap grow quadratically.

Why += often looks fine in practice

Runtimes try to rescue you. CPython can grow a string in place when nothing else references it, but PEP 8 says not to rely on that. V8 represents a + b as a lazy “rope” node and flattens it later. C# does neither: += in a loop is genuinely quadratic. In an interview, write the builder version and say why.

When to reach for it

The problem says…	The tool
“build an output string”, “encode”, “format”	List of parts + join, or a StringBuilder.
“letters a-z”, “shift by k”, “index of a letter”	Char codes: ord(ch) - ord('a'), charCodeAt, ch - 'a'.
“words separated by spaces”, “parse fields”	split (know its edge cases) or a hand-rolled scanner.
“modify characters in place”	Convert to a list / char[], edit, convert back.
“substring that…”, “contiguous run of chars”	Indices plus two pointers or a sliding window, not repeated slicing.
“find a pattern in text”	Built-in in / includes / Contains, or string algorithms (KMP, rolling hash).

How it works

Splitting and joining

1. Split into tokens. Know whether empty fields are kept.
2. Transform the tokens as a list (an ordinary mutable array).
3. Join once at the end.

Python

reverse_words.py

def reverse_words(s: str) -> str:
    """'  the sky  is blue ' -> 'blue is sky the' (collapse runs of spaces)."""
    words = s.split()  # 1. no-arg split: splits on whitespace runs, drops empty strings
    words.reverse()  # 2. reverse the list in place, O(n)
    return " ".join(words)  # 3. one allocation for the result, not one per word


def split_keep_empty(s: str, sep: str) -> list[str]:
    return s.split(sep)  # with an explicit separator, empty fields are kept


if __name__ == "__main__":
    assert reverse_words("  the sky  is blue ") == "blue is sky the"
    assert reverse_words("") == ""
    assert split_keep_empty("a,,b", ",") == ["a", "", "b"]
    assert split_keep_empty("", ",") == [""]  # not []!
    assert "".split() == []
    print("ok")

TypeScript

reverse_words.ts

import assert from "node:assert/strict";

/** '  the sky  is blue ' -> 'blue is sky the' (collapse runs of spaces). */
export function reverseWords(s: string): string {
  const words = s.split(/\s+/).filter((w) => w.length > 0); // 1. regex split, then drop empties
  words.reverse(); // 2. Array.prototype.reverse is in place
  return words.join(" "); // 3. one result string, not one per word
}

assert.equal(reverseWords("  the sky  is blue "), "blue is sky the");
assert.equal(reverseWords(""), "");
assert.deepEqual("a,,b".split(","), ["a", "", "b"]); // empty fields are kept
assert.deepEqual("".split(","), [""]); // not []!
assert.deepEqual("a,b,c".split(",", 2), ["a", "b"]); // JS limit truncates (unlike Python maxsplit)
console.log("ok");

C#

reverse_words.cs

// "  the sky  is blue " -> "blue is sky the" (collapse runs of spaces).
static string ReverseWords(string s)
{
    // 1. RemoveEmptyEntries drops the "" fields that repeated spaces produce
    string[] words = s.Split(' ', StringSplitOptions.RemoveEmptyEntries);
    Array.Reverse(words);              // 2. reverse in place
    return string.Join(' ', words);    // 3. one allocation for the result
}

if (ReverseWords("  the sky  is blue ") != "blue is sky the") throw new Exception("bad reverse");
if (ReverseWords("") != "") throw new Exception("expected empty");
if (!"a,,b".Split(',').SequenceEqual(["a", "", "b"])) throw new Exception("empties kept by default");
if ("".Split(',').Length != 1) throw new Exception("\"\".Split gives [\"\"]");
if (!"a,b,c".Split(',', 2).SequenceEqual(["a", "b,c"])) throw new Exception("C# count keeps the rest");
if (!" a , b ".Split(',', StringSplitOptions.TrimEntries).SequenceEqual(["a", "b"])) throw new Exception("trim");
Console.WriteLine("ok");

split is the most edge-case-dense call in this whole topic:

Input	Python	TypeScript	C#
"a,,b" split on ,	['a', '', 'b']	['a', '', 'b']	["a", "", "b"]
"" split on ,	['']	['']	[""]
" a b " on whitespace	s.split() → ['a', 'b']	s.split(/\s+/) → ['', 'a', 'b', '']	Split(' ', RemoveEmptyEntries) → ["a", "b"]
limit of 2 on "a,b,c"	split(',', 1) → ['a', 'b,c']	split(',', 2) → ['a', 'b'] (truncates)	Split(',', 2) → ["a", "b,c"]
trim each field	[f.strip() for f in …]	.map(f => f.trim())	StringSplitOptions.TrimEntries (.NET 5+)

Characters are numbers

1. Get the code: ord(ch) (Python), s.charCodeAt(i) (TS), (int)ch or just ch - 'a' (C#).
2. Do arithmetic: offset, mod 26, compare ranges.
3. Turn it back: chr(n), String.fromCharCode(n), (char)n.

Python

to_title / to_number.py

def to_title(n: int) -> str:
    """Spreadsheet column: 1 -> 'A', 26 -> 'Z', 27 -> 'AA', 703 -> 'AAA'."""
    parts: list[str] = []  # 1. collect pieces in a list; join once at the end
    while n > 0:
        n -= 1  # 2. bijective base 26: shift to 0..25 before each digit
        parts.append(chr(ord("A") + n % 26))
        n //= 26
    return "".join(reversed(parts))  # 3. digits came out least-significant first


def to_number(title: str) -> int:
    n = 0
    for ch in title:
        n = n * 26 + (ord(ch) - ord("A") + 1)  # 4. char code arithmetic: 'A' -> 1
    return n


if __name__ == "__main__":
    for n, t in [(1, "A"), (26, "Z"), (27, "AA"), (52, "AZ"), (703, "AAA")]:
        assert to_title(n) == t and to_number(t) == n
    assert all(to_number(to_title(n)) == n for n in range(1, 2000))
    print("ok")

TypeScript

to_title / to_number.ts

import assert from "node:assert/strict";

const A = "A".charCodeAt(0); // 65

/** Spreadsheet column: 1 -> 'A', 26 -> 'Z', 27 -> 'AA', 703 -> 'AAA'. */
export function toTitle(n: number): string {
  const parts: string[] = []; // 1. collect pieces in an array; join once at the end
  while (n > 0) {
    n -= 1; // 2. bijective base 26: shift to 0..25 before each digit
    parts.push(String.fromCharCode(A + (n % 26)));
    n = Math.floor(n / 26);
  }
  return parts.reverse().join(""); // 3. digits came out least-significant first
}

export function toNumber(title: string): number {
  let n = 0;
  for (let i = 0; i < title.length; i++) n = n * 26 + (title.charCodeAt(i) - A + 1); // 4. 'A' -> 1
  return n;
}

for (const [n, t] of [[1, "A"], [26, "Z"], [27, "AA"], [52, "AZ"], [703, "AAA"]] as const) {
  assert.equal(toTitle(n), t);
  assert.equal(toNumber(t), n);
}
for (let n = 1; n < 2000; n++) assert.equal(toNumber(toTitle(n)), n);
console.log("ok");

C#

to_title / to_number.cs

using System.Text;

// Spreadsheet column: 1 -> "A", 26 -> "Z", 27 -> "AA", 703 -> "AAA".
static string ToTitle(int n)
{
    var sb = new StringBuilder();        // 1. mutable buffer; one string at the end
    while (n > 0)
    {
        n--;                             // 2. bijective base 26: shift to 0..25 before each digit
        sb.Insert(0, (char)('A' + n % 26)); // 3. prepend (titles are short, so O(k²) is fine here)
        n /= 26;
    }
    return sb.ToString();
}

static int ToNumber(string title)
{
    int n = 0;
    foreach (char ch in title) n = n * 26 + (ch - 'A' + 1); // 4. char arithmetic: 'A' -> 1
    return n;
}

foreach (var (n, t) in new[] { (1, "A"), (26, "Z"), (27, "AA"), (52, "AZ"), (703, "AAA") })
    if (ToTitle(n) != t || ToNumber(t) != n) throw new Exception($"bad {n} {t}");
for (int n = 1; n < 2000; n++)
    if (ToNumber(ToTitle(n)) != n) throw new Exception($"round trip {n}");
Console.WriteLine("ok");

But “one character” means different things. Python strings are sequences of code points. JS and C# strings are sequences of UTF-16 code units, so an emoji outside the Basic Multilingual Plane is two units (a surrogate pair). What a person sees as one character (a grapheme) can be several code points: a base letter plus a combining accent, or an emoji plus a skin-tone modifier. Type something:

Characters, code points, code units, bytes

type anything

text (try an emoji, an accent, a flag)

you see	code points (Python ord)	UTF-16 units (JS / C# char)	UTF-8 bytes
C	U+0043	0043	43
a	U+0061 (ord−97 = 0)	0061	61
f	U+0066 (ord−97 = 5)	0066	66
é	U+00E9	00E9	C3 A9
␣	U+0020	0020	20
👍🏽	U+1F44D U+1F3FD	D83D DC4D D83C DFFD ← surrogate pair	F0 9F 91 8D F0 9F 8F BD
␣	U+0020	0020	20
o	U+006F (ord−97 = 14)	006F	6F
k	U+006B (ord−97 = 10)	006B	6B

Python len(s)10

JS s.length / C# s.Length12

UTF-8 bytes17

graphemes (what users see)9

JS s.split('').reverse().join(''): ko �🁍� éfaC

JS [...s].reverse().join('') / Python s[::-1]: ko 🏽👍 éfaC

Highlighted rows take more than one unit. Reversing by UTF-16 unit splits surrogate pairs into garbage (�); reversing by code point keeps emoji whole but still detaches skin-tone modifiers and combining accents. For ASCII-only input (most interview problems) all four counts agree. Ask.

The string API you need, side by side

	Python	TypeScript	C#
length	len(s) (code points)	s.length (UTF-16 units)	s.Length (UTF-16 units)
char at i	s[i] (a 1-char str)	s[i] / s.charAt(i)	s[i] (a char)
substring	s[i:j] (copy)	s.slice(i, j)	s[i..j] / Substring(i, len) (copy); AsSpan(i, len) (no copy)
find	s.find(t) (-1) / s.index(t) (raises)	s.indexOf(t)	s.IndexOf(t, StringComparison.Ordinal)
mutable copy	list(s)	[...s] / s.split('')	s.ToCharArray()
back to string	"".join(chars)	chars.join('')	new string(chars)
letter / digit test	ch.isalpha(), ch.isdigit()	regex /[a-z]/i.test(ch)	char.IsLetter(ch), char.IsDigit(ch)
case	s.lower(), s.casefold()	s.toLowerCase()	s.ToLowerInvariant()
equality	== (value)	=== (value, for primitives)	== (value, ordinal)

What it costs

Operation	Cost	Note
index s[i]	O(1)	Python stores code points in a fixed width per string, so this is O(1) too.
length	O(1)
slice / substring of k chars	O(k)	A copy, except C# Span / ReadOnlyMemory.
a + b	O(len(a) + len(b))	New string.
n appends with +=	O(n²) worst	Total characters copied grows quadratically.
n appends with builder / join	O(n)	Amortized doubling, one final copy.
t in s / includes / Contains	O(len(s) · len(t)) worst	Implementations use fast heuristics, but don’t claim O(n) without saying so.
compare / hash	O(length)	Hashing a long key isn’t free.
split, join, replace, lower	O(n)	Each allocates a new result.

The interview trap is the hidden O(n) inside a loop: slicing s[1:] in recursion, s.replace per character, or building with +=. Pass indices instead of substrings and build with a builder.

Variations you’ll meet

• Mutable char buffers: list(s) / char[] for in-place reversal or swapping, then convert back once.
• Fixed alphabet tables: int[26] counts indexed by ch - 'a'. See counting.
• Scanning parsers: walk an index through the string, reading digits, names and separators. See parsing.
• Interning: identical string literals may share one object. Use == for value equality in Python and C#; never is (Python) or ReferenceEquals (C#).
• Byte strings: Python bytes/bytearray, JS Uint8Array + TextEncoder, C# byte[] + Encoding.UTF8. Needed whenever sizes are in bytes (network, files, token budgets).

Pitfalls

• Quadratic building with +=, especially in C#.
• Off-by-one in slices. Python and JS end indices are exclusive; C# Substring(start, length) takes a length, not an end.
• Culture-sensitive comparison in C#. string.Compare, StartsWith(string) and ToLower() use the current culture by default; pass StringComparison.Ordinal or use ToLowerInvariant. (The classic bug: Turkish dotless i.)
• JS default sort compares UTF-16 units: ["b", "a", "B"].sort() gives ["B", "a", "b"]. Same for Python and C# ordinal sorts: uppercase sorts before lowercase.
• Surrogate pairs. s.split('') and s[i] in JS/C# can split an emoji in half.
• Python str.isdigit() is true for characters like '²'. For ASCII digits specifically, compare against '0' <= ch <= '9'.

In the interview

• Ask about the character set: “ASCII only? Lowercase letters? Unicode?” It decides int[26] vs a map, and whether length means characters or bytes.
• Ask about whitespace and empty input: leading/trailing spaces, repeated separators, empty string.
• Say out loud when you choose a builder: “Strings are immutable, so I collect parts and join once: O(n) instead of O(n²).”
• Pass indices, not substrings, into helpers and recursion, and say why.
• Follow-ups to expect: “the input is a 10 GB file” (stream it line by line), “now support Unicode” (code points vs graphemes).

Check yourself

Check yourself

pick one

A C# loop runs `result += word + " ";` for 100,000 words of about 5 characters. Roughly how many characters get copied in total?

AAbout 600,000BAbout 3 × 10¹⁰CAbout 100,000

Check yourself

pick one

In JavaScript, what is "👍".length?

A1B2C4

Check yourself

pick one

You recurse with helper(s[1:]) on a string of length n. Ignoring the recursion's own work, what do the slices cost in total?

AO(n)BO(n log n)CO(n²)

Practice on your own

Classic textbook exercises, not gym questions:

• Longest common prefix of a list of words.
• Basic string compression: "aabcccccaaa" → "a2b1c5a3", returning the original if it isn’t shorter.
• Is t a rotation of s? (one in check, if you see the trick)
• Caesar cipher: shift letters by k, keeping case and leaving other characters alone.

Go deeper

• Python docs, Text sequence type str (split semantics, join) and PEP 8 on string concatenation.
• MDN, String: UTF-16 characters, code points and grapheme clusters.
• Microsoft Learn, Character encoding in .NET and Best practices for comparing strings.
• Joel Spolsky, “The Absolute Minimum Every Software Developer Must Know About Unicode”.

Related

ArraysThe buffer under every builder.

CountingLetter tables indexed by char code.

ParsingScanning text with an index.

String algorithmsKMP, rolling hashes, pattern search.