FundamentalsData structureaka character array, text, char sequence

String

An immutable (in most languages) sequence of characters stored as an array, with its own family of matching and counting algorithms.

Pattern: Two Pointers Practice (9)

Progress

Definition

A string is an Array of characters. Indexing, slicing and scanning behave exactly like an array, but two things make strings their own topic: in Python, Java, JavaScript and Go they are immutable (every "modification" allocates a new string), and there is a rich set of algorithms specific to text — substring search (Knuth–Morris–Pratt (KMP), Rabin–Karp, Z-Algorithm), palindromes (Manacher's Algorithm), and prefix-based lookups (Trie).

Immutability has a concrete cost: building a string by repeated s += c copies the growing prefix each time, O(n²) total. The fix is to accumulate pieces in a Dynamic Array (or StringBuilder) and join once.

Encoding matters too. In Python and Java len(s) counts UTF-16 code units or code points, not user-visible characters; in Go a string is a byte slice and len("é") is 2. Interview problems almost always assume ASCII or lowercase a-z, which makes a 26- or 128-slot count array the natural frequency structure.

charactersimmutabletextpattern matchingunicode

Intuition

A mental model before the formal terms.

Think of a string as a row of Scrabble tiles glued to a board. You can read any tile instantly and slide a frame along the row to inspect windows of tiles, but you cannot push a new tile into the middle without unsticking and re-gluing every tile after it — and in immutable languages you must build a whole new board.

Most string problems reduce to two things: counting letters (an array of 26 ints is a tiny hash map) and comparing substrings efficiently (hashing or a precomputed failure table so you never re-compare characters you have already seen).

How it works

Storage: a contiguous array of fixed-width code units (1 byte for ASCII/UTF-8 bytes, 2 bytes for UTF-16) plus a length. s[i] is O(1) for fixed-width encodings.
Comparison: s == t compares lengths first, then characters left to right — O(min(|s|, |t|)).
Concatenation s + t allocates |s| + |t| and copies both; slicing s[i:j] copies j - i characters (some runtimes share the buffer instead).
Substring search s.find(p): naive is O(n·m); Knuth–Morris–Pratt (KMP) / Z-Algorithm achieve O(n + m) by precomputing how far the pattern can shift after a mismatch; Rabin–Karp compares rolling hashes.
Frequency analysis: map each character to an index (ord(c) - ord('a')) and count in an int array — the backbone of anagram, sliding-window and "valid permutation" problems.

Why it works

Because a string is an array, every array technique transfers: two pointers for palindromes/reversal, sliding windows over character counts, prefix arrays over the text.

Immutability makes strings safe hash keys (their hash never changes) and lets runtimes intern and share them, which is why dict/HashMap keyed by string is so common.

Linear-time matching works because a mismatch at position i after matching k characters reveals information about those k characters — the failure function reuses it so the text pointer never moves backwards.

Operations

Operation	Description	Cost
charAt(i)	Index into the underlying character array.	O(1)
length()	Stored alongside the buffer.	O(1)
concat(s, t)	Allocate a new buffer and copy both operands.	O(\|s\| + \|t\|)
substring(i, j)	Copy `j - i` characters into a new string.	O(j - i)
compare(s, t)	Character-by-character until first difference.	O(min(\|s\|, \|t\|))
find(pattern)	Naive `O(n·m)`; KMP / Z / Rabin–Karp `O(n + m)`.	O(n + m)
hash(s)	Polynomial rolling hash over all characters; cached by many runtimes.	O(n)
split / join	Single pass over the text producing or consuming pieces.	O(n)

Recognition

How to tell a problem wants this.

Input is text: words, DNA sequences, parentheses, digits as characters.
Words like "substring", "anagram", "palindrome", "prefix/suffix", "pattern occurs in text", "rotate the string".
A small alphabet (a-z, digits, ACGT) — use a fixed-size count array rather than a general Hash Map.

“sorted array” → Two Pointers “contiguous subarray” → Sliding Window “have you seen this before” → Hashing “prefix” → Trie

Interactive demo

Play, step, change the input. ← → and space work too.

No interactive visualization for this topic yet

Related visualizations are linked under Related.

Pseudocode

1class Str:
2  chars = array of code units; n = length
3  charAt(i): return chars[i]
4  concat(t): out = allocate(n + t.n); copy chars then t.chars; return out
5  substring(i, j): out = allocate(j - i); copy chars[i..j-1]; return out
6  equals(t): if n != t.n return false; for i in 0..n-1: if chars[i] != t.chars[i] return false; return true
7  find(p): for i in 0..n-m: if chars[i..i+m-1] == p return i; return -1
8  charCounts(): cnt[26] = 0; for c in chars: cnt[c - "a"] += 1; return cnt

Implementation

11 · Concatenate (allocate n + m, copy both)
2def concat(a: str, b: str) -> str:
3    return a + b
4 
5 
62 · Substring by copying [i, j)
7def substring(s: str, i: int, j: int) -> str:
8    return s[i:j]  # slicing copies
9 
10 
113 · Equality (length check, then char-by-char)
12def equals_manual(a: str, b: str) -> bool:
13    if len(a) != len(b):
14        return False
15    for k in range(len(a)):
16        if a[k] != b[k]:
17            return False
18    return True
19 
20 
214 · Naive find (O(n*m))
22def find_naive(s: str, p: str) -> int:
23    n, m = len(s), len(p)
24    for i in range(n - m + 1):
25        k = 0
26        while k < m and s[i + k] == p[k]:
27            k += 1
28        if k == m:
29            return i
30    return -1
31 
32 
335 · Character counts over a-z
34def char_counts(s: str) -> list[int]:
35    cnt = [0] * 26
36    for c in s:
37        cnt[ord(c) - ord("a")] += 1
38    return cnt
39 
40 
416 · Reverse via list (strings are immutable)
42def reverse(s: str) -> str:
43    chars = list(s)
44    l, r = 0, len(chars) - 1
45    while l < r:
46        chars[l], chars[r] = chars[r], chars[l]
47        l, r = l + 1, r - 1
48    return "".join(chars)

Walkthrough

a + b allocates a new string of length n + m; CPython has an optimisation for s += t when s has one reference, but do not rely on it.
s[i:j] copies the slice — there is no view type for str.
equals_manual is what == does in C: length check, then memcmp.
find_naive is the textbook loop behind s.find(p) / p in s (CPython uses a two-way/Crochemore-Perrin hybrid for long patterns).
ord(c) - ord("a") maps to a 0..25 bucket; collections.Counter(s) is the general tool.
reverse goes through a list because str is immutable; s[::-1] is the idiom.

Complexity (this implementation)

time O(n + m) concat, O(j - i) substring, O(n*m) naive find · space O(n) for copies

Slicing always copies, so s[1:] in a recursive function costs O(n) per call; pass indices instead.

Language notes

str is immutable and indexed by Unicode code point, not byte — len("é") is 1.
Build strings with "".join(parts); s += piece in a loop is O(n^2) in the worst case.
in, find, startswith, count cover most substring queries.
bytes/bytearray are the mutable byte-oriented alternatives.

Common mistakes in this language

s[0] = "x" raises TypeError; convert to a list first.
Repeated slicing in a loop (while s: s = s[1:]) is quadratic.
Comparing str with bytes — always False, never equal.

Language differences that matter here

Mutability: C++ std::string is mutable (in-place reverse, s[i] = c); JS/TS and Python strings are immutable — every edit allocates.
Unit of indexing: C++ bytes, JS/TS UTF-16 code units (emoji take two), Python Unicode code points.
Zero-copy views: C++ std::string_view exists; JS and Python slices always copy.
Repeated concatenation: O(n^2) in C++ with s = s + c (use +=), amortized in V8 via ropes, potentially O(n^2) in Python (use "".join).

Complexity

Operation	Average	Worst	Note
Access	O(1)	O(1)	For fixed-width encodings.
Search	O(n + m)	O(n·m)	Naive worst case; KMP/Z guarantee O(n + m).
Insert	O(n)	O(n)	Creates a new string in immutable languages.
Delete	O(n)	O(n)
Update	O(n)	O(n)	O(1) only for mutable char arrays.
Concatenate	O(\|s\| + \|t\|)	O(\|s\| + \|t\|)
Compare	O(min(\|s\|, \|t\|))	O(min(\|s\|, \|t\|))
Hash	O(n)	O(n)	Often cached after first computation.
Space	O(n)

Advantages & disadvantages

Advantages

All the benefits of arrays: O(1) indexing, compact contiguous storage, fast scans.
Immutability makes strings safe as hash keys and free to share between references.
Extensive built-in library support (search, split, format) in every language.

Disadvantages

Immutable strings make repeated concatenation O(n²) unless you use a builder.
Unicode complicates "characters": code units, code points and grapheme clusters differ.
Substring search is O(n·m) naively; linear-time algorithms require preprocessing and care.
Insert/delete in the middle is O(n) like any array; a rope or gap buffer is needed for editor-scale mutation.

Use cases

Text processing: parsing, tokenizing, validating input formats.
Keys in Hash Map and Hash Set (word counts, deduplication, anagram grouping via sorted key).
Pattern matching and search: Knuth–Morris–Pratt (KMP), Rabin–Karp, Aho–Corasick, Suffix Array.
Prefix structures: autocomplete and spell-check via Trie.
DP over sequences: Longest Common Subsequence, Edit Distance, palindromic substrings.

Use it when

Any text input; use built-in string operations for clarity when n is small.
As hash keys for grouping (anagrams by sorted string or count signature).
Convert to a mutable char array/list when you need many in-place edits, then join once.

Avoid it when

Heavy middle insertion/deletion (text editors) — use a rope, gap buffer, or a list of chunks.
Building output via repeated += in a loop — accumulate in a list/StringBuilder.
Many substring-equality checks — precompute a Rolling Hash (Polynomial Hashing) or Suffix Array instead of slicing.

Alternatives

Array Dynamic Array Trie Suffix Array

Common mistakes

Quadratic string building with s += c inside a loop in Python/Java/JS.
Treating s[i] as O(1) for Go strings containing multibyte UTF-8 runes, or counting bytes instead of characters.
Comparing with == in Java (reference equality) instead of .equals.
Using str.find / indexOf inside a loop without noticing the total becomes O(n²).
Forgetting that slicing copies — s[i:] inside recursion turns O(n) into O(n²).
Off-by-one in substring bounds (inclusive vs exclusive end).

Interview patterns

Frequency count with a 26-int array for anagrams, permutation-in-string, character replacement.
Two pointers from both ends for palindrome checks and reversal in place.
Sliding window with a count map for longest substring without repeats / minimum window.
Expand-around-centre or Manacher's Algorithm for palindromic substrings.
Sorted string or count tuple as the canonical key when grouping anagrams.
Prefix/failure table (Knuth–Morris–Pratt (KMP)) for repeated pattern or "shortest palindrome" tricks.

Interview questions on this

Recognizing the approach from an array and a targetIntermediate
Deciding whether O(n²) can be improvedIntermediate
Hash map or array?Beginner
Average case versus worst caseIntermediate

Mock interviews

Minimum Size Subarray SumIntermediate
Two SumBeginner
Longest Substring Without Repeating CharactersIntermediate

Interview problems

Group Anagramsmedium Repeated DNA Sequencesmedium Longest Substring Without Repeating Charactersmedium Minimum Window Substringhard Longest Repeating Character Replacementmedium Permutation in Stringmedium Valid Parentheseseasy Longest Palindromic Substringmedium Find the Index of the First Occurrenceeasy