Strings

A string is just an array of characters — but Python makes that array immutable, and that single fact quietly shapes almost every string pattern you’ll write.

What you’ll learn

• Why strings are immutable, and why that makes s += chunk in a loop $O(n^2)$ overall.
• Why building a list of pieces and calling "".join(...) is $O(n)$.
• ord/chr, ASCII, slicing, and one-line reversal.
• Complexity of common string operations.
• The anagram and palindrome patterns, runnable and ready to reuse.
• LeetCode-style problems to drill the pattern.

The cue

The one thing that makes Python strings different: immutability

Every “modification” allocates a new string. That single fact drives almost every performance decision here:

• s += ch in a loop is $O(n^2)$ — each concatenation copies the whole string. Collect into a list and "".join(parts) at the end for $O(n)$.
• Slicing copies. s[1:] inside a recursion is a hidden $O(n^2)$; pass indices instead.
• In-place two-pointer algorithms need list(s) first, then "".join.

Otherwise treat a string as an array of characters with the usual patterns — two pointers, sliding window, frequency maps — and remember that a bounded alphabet is what makes those frequency maps $O(1)$ space.

Strings are immutable

Every “modification” of a Python str actually builds a brand-new string — the original is never changed in place.

immutability.py

s = "hello"
t = s.upper()
 
print("original s:", s)   # unchanged
print("new string t:", t)
print("same object?", s is t)
 
# there is no s[0] = "H" — strings don't support item assignment
try:
    s[0] = "H"
except TypeError as e:
    print("TypeError:", e)

The += trap: O(n) per step, O(n^2) total

Because each += builds a whole new string, concatenating in a loop copies more and more characters every iteration.

concat_trap.py

# O(n^2) total: each += copies the ENTIRE string built so far
def build_slow(n):
    s = ""
    for i in range(n):
        s += str(i)   # new string of growing length, every time
    return s
 
 
# O(n) total: collect pieces, join ONCE
def build_fast(n):
    parts = []
    for i in range(n):
        parts.append(str(i))   # O(1) amortized append to a list
    return "".join(parts)       # one O(n) join at the end
 
 
print(build_slow(5))
print(build_fast(5))
print(build_slow(5) == build_fast(5))

$$\underbrace{1 + 2 + 3 + \dots + n}_{\text{copy cost per } \texttt{+=}} = O(n^2) \qquad\text{vs.}\qquad \underbrace{O(n)}_{\text{one join}}$$

The single most common string mistake

s += chunk inside a loop looks harmless and passes on small inputs. On a judge with large n it silently becomes $O(n^2)$ and times out. Always collect pieces in a list and "".join(...) once.

ord, chr, and ASCII

Characters are just small integers under the hood — ord and chr convert between a character and its code point.

ord_chr.py

print(ord("a"), ord("z"), ord("A"))
print(chr(97), chr(122), chr(65))
 
# classic trick: map a lowercase letter to an index 0-25
def letter_index(c):
    return ord(c) - ord("a")
 
print(letter_index("a"), letter_index("m"), letter_index("z"))
 
# shift a letter (Caesar-cipher style), wrapping within a-z
def shift_letter(c, k):
    base = ord("a")
    return chr((ord(c) - base + k) % 26 + base)
 
print(shift_letter("x", 3))   # wraps past 'z'

Slicing and reversal

Slicing works on strings exactly like it does on lists — and reversal is one line.

string_slicing.py

s = "algorithms"
 
print(s[1:5])     # substring
print(s[::-1])    # reversed copy, O(n)
print(s[-3:])     # last 3 characters
print(s[::2])     # every other character
 
print(s == s[::-1])   # palindrome check in one line

Complexity of common string operations

Operation	Example	Complexity
Index access	s[i]	$O(1)$
Slice of length $k$	s[a:b]	$O(k)$
Concatenation	s1 + s2	$O(n + m)$
+= in a loop, $n$ times	s += chunk	$O(n^2)$ total
"".join(parts)	one call	$O(n)$ total
Search substring	x in s	$O(n \cdot m)$ worst case
Length	len(s)	$O(1)$

Pattern: anagram check

Two strings are anagrams if they contain the same characters with the same frequency. Sorting both is the simplest correct approach; counting is faster for long strings.

anagram_check.py

from collections import Counter
 
 
def is_anagram_sort(a, b):
    # O(n log n) — simple and clear
    return sorted(a) == sorted(b)
 
 
def is_anagram_count(a, b):
    # O(n) — compare character frequency counts
    return Counter(a) == Counter(b)
 
 
print(is_anagram_sort("listen", "silent"))
print(is_anagram_count("listen", "silent"))
print(is_anagram_count("rat", "car"))

Pattern: palindrome check

A palindrome reads the same forwards and backwards. Two pointers converging from both ends avoid building a reversed copy.

palindrome_check.py

def is_palindrome(s):
    left, right = 0, len(s) - 1
    while left < right:
        if s[left] != s[right]:
            return False
        left += 1
        right -= 1
    return True
 
 
def is_palindrome_alnum_only(s):
    # ignore case and non-alphanumeric characters, e.g. "A man, a plan..."
    cleaned = [c.lower() for c in s if c.isalnum()]
    return cleaned == cleaned[::-1]
 
 
print(is_palindrome("racecar"))
print(is_palindrome("hello"))
print(is_palindrome_alnum_only("A man, a plan, a canal: Panama"))

LeetCode problem set

Generated from the problem database, so each entry carries its sheet membership and reported companies. Tick them off as you go — progress is saved in this browser, and the Export button writes it to a file you can keep.

11 problems

6 easy4 medium1 hard

Work down the ladder. Tick each problem off as you go — progress is saved in this browser, and the Export button in the filter bar writes it to a file you can keep.

AllEasyMediumHard

Unsolved onlyExportImportReset

• ○242Valid Anagrameasy`Counter(s) == Counter(t)`, or a 26-slot tally when you must avoid the importNeetCode 150Blind 75LeetCode Top Interview 150amazonmetabloomberg
• ○13Roman to IntegereasyLeetCode Top Interview 150
• ○14Longest Common PrefixeasyCompare column by column and stop at the first mismatch -- no sorting neededLeetCode Top Interview 150
• ○58Length of Last WordeasyLeetCode Top Interview 150
• ○125Valid PalindromeeasyFilter to alphanumerics and lowercase, then close in from both endsNeetCode 150Blind 75LeetCode Top Interview 150
• ○169Majority ElementeasyLeetCode Top Interview 150
• ○12Integer to RomanmediumLeetCode Top Interview 150
• ○151Reverse Words in a StringmediumLeetCode Top Interview 150
• ○271Encode and Decode StringspremiummediumNeetCode 150Blind 75
• ○274H-IndexmediumLeetCode Top Interview 150
• ○135CandyhardLeetCode Top Interview 150

Visual intuition

A string is an array of characters, so the same steppers apply. Here the centre-expansion pattern:

arrayA string is an array of charactersLC 5 · O(n^2) time, O(1) space

b0a1b2a3d4

1def longest_palindrome(s):2    best = (0, 0)3    for c in range(len(s)):4        for lo, hi in ((c, c), (c, c + 1)):     # odd, then even5            while lo >= 0 and hi < len(s) and s[lo] == s[hi]:6                lo -= 1; hi += 17            lo, hi = lo + 1, hi - 1             # step back inside8            if hi - lo > best[1] - best[0]:9                best = (lo, hi)10    return s[best[0]:best[1] + 1]

centres9

setupA palindrome is defined by its **centre**, and there are only $2n - 1$ centres: $n$ single characters (odd lengths) and $n - 1$ gaps between characters (even lengths). Checking every substring is $O(n^3)$; expanding from every centre is $O(n^2)$ with no extra memory.

Play‹›1/19⟲

Both centre kinds must be tried at every index — n single characters for odd lengths and n-1 gaps for even ones. Checking only odd centres misses 'abba' and still passes many tests.

Practice — real LeetCode problems

Each exercise is the actual LeetCode problem with its real method signature and LeetCode’s own examples as the test. Write the body, press Run, and match the expected output.

LC 344 — Reverse String · Easy

Problem. Reverse a list of characters in place with $O(1)$ extra memory.

Constraints. 1 <= len(s) <= 10^5, printable ASCII.

Examples. ["h","e","l","l","o"] gives ["o","l","l","e","h"]

pch.exerciseTag pch.exerciseTitle

Editorial

Swap the outermost pair and move inward. while left < right handles both parities: for an odd length the pointers land on the same index and the loop stops, correctly leaving the middle character alone.

Time $O(n)$. Space $O(1)$.

Python’s own s.reverse() is the idiomatic in-place answer, and s[::-1] allocates a copy so it violates the stated constraint. Say both, then write the loop — the question exists to check the pointer mechanics.

Follow-ups: “Reverse only the vowels (LC 345)?” — same two pointers, skipping non-vowels. “Reverse words in a string (LC 151)?” — below. “Reverse a linked list (LC 206)?” — pointer rewiring instead of index swapping.

LC 14 — Longest Common Prefix · Easy

Problem. Find the longest common prefix shared by all strings in an array. Return "" if there is none.

Constraints. 1 <= len(strs) <= 200, 0 <= len(strs[i]) <= 200, lowercase letters.

Examples. ["flower","flow","flight"] gives "fl" · ["dog","racecar","car"] gives ""

pch.exerciseTag pch.exerciseTitle

Editorial

The answer can never be longer than the first string, so use it as an upper bound and trim it against each word.

Time $O(\text{total characters})$ in the worst case. Space $O(1)$ beyond the output.

["ab","a"] giving "a" is the case worth checking: the shorter word forces the prefix down, so nothing may assume the first string is the shortest.

The vertical-scanning alternative — compare character i across all words, stop at the first mismatch — is equally good and often clearer. A third option is to sort and compare only the first and last strings, since they differ most; that is $O(n \log n)$ but a nice observation.

Follow-ups: “Longest common suffix?” — reverse everything and reuse this. “Many queries against a growing dictionary?” — a trie: the common prefix is the path before the first branch. “Longest common substring?” — a much harder DP problem.

LC 151 — Reverse Words in a String · Medium

Problem. Reverse the order of the words in s. Words are separated by one or more spaces. The result must have single spaces between words and no leading or trailing spaces.

Constraints. 1 <= len(s) <= 10^4, letters, digits and spaces, and there is at least one word.

Examples. "the sky is blue" gives "blue is sky the" · " hello world " gives "world hello" · "a good example" gives "example good a"

pch.exerciseTag pch.exerciseTitle

Editorial

s.split() with no separator splits on arbitrary whitespace runs and drops leading and trailing empties, which is precisely the normalisation the problem asks for.

Time $O(n)$. Space $O(n)$.

The distinction that matters: "a b".split() gives ['a', 'b'], while "a b".split(" ") gives ['a', '', 'b']. The second form keeps the empty token and would put a stray double space in the output. Knowing that difference is the Python content of this problem.

Because Python strings are immutable, a genuinely $O(1)$-space in-place solution is not possible here. In C++ the expected approach is to reverse the whole string, then reverse each word in place — a neat trick worth describing if asked, and it is the reason this problem is rated Medium.

Follow-ups: “Do it in $O(1)$ space?” — impossible with immutable strings; describe the reverse-all-then-reverse-each approach for a mutable buffer. “Reverse the characters of each word but keep word order (LC 557)?” — split, reverse each, rejoin. “Without built-ins?” — scan manually for word boundaries and build a list.

Dry run

Why += in a loop is quadratic. Building a 5-character string:

step	operation	characters copied
1	"" + "a"	1
2	"a" + "b"	2
3	"ab" + "c"	3
4	"abc" + "d"	4
5	"abcd" + "e"	5

Total 15 copies for 5 characters — the sum $1 + 2 + \dots + n$, which is $O(n^2)$. With "".join(parts) there is one allocation and $n$ copies.

At $n = 10^5$ that is 5 billion character copies versus 100,000 — the difference between a TLE and an instant pass, from one line.

CPython sometimes optimises s += ch, and you should not rely on it

When a string has exactly one reference, CPython can resize in place, making the loop look linear. The optimisation silently disappears if anything else holds a reference — so the quadratic behaviour is real, just intermittent. Use join.

The variant map

Task	Approach	Complexity
Build a string piecewise	list of parts + "".join	$O(n)$
Reverse, or palindrome check	two pointers on list(s)	$O(n)$ time, $O(n)$ space in Python
Count characters	collections.Counter	$O(n)$ time, $O(1)$ space for a bounded alphabet
Anagram grouping	sorted string, or a 26-tuple, as the key	$O(n \log k)$ or $O(n)$ per word
Substring search	in (uses a tuned algorithm), or KMP by hand	$O(n + m)$
Longest palindromic substring	expand around centre	$O(n^2)$ time, $O(1)$ space
Tokenise or parse	a stack, character by character	$O(n)$

Python specifics worth stating: str.split() with no argument splits on any whitespace and drops empties, which is usually what you want; str.isalnum() and str.lower() handle the LC 125 skip conditions without manual ASCII arithmetic; and ord(c) - ord('a') is the index into a 26-slot count array.

Interview follow-ups

They ask	What they’re checking	The answer
“Why is s += ch in a loop slow?”	Immutability awareness	Each concatenation copies the whole string, so total work is $1 + 2 + \dots + n = O(n^2)$. Use a list and join
“Reverse a string in place”	Language honesty	Impossible in Python — strings are immutable. Convert with list(s), two-pointer swap, then "".join. Say the $O(n)$ space is a language cost, not an algorithmic one
“Space complexity of your frequency map?”	Precision	$O(1)$ for a bounded alphabet — at most 26 keys. For arbitrary Unicode it is $O(\min(n, \lvert\Sigma\rvert))$
“Is in for substring search $O(n \cdot m)$?”	Depth	CPython uses a tuned mixed algorithm that is effectively linear in practice. Worst case is not the naive bound, but if asked to implement it, write KMP
“Handle Unicode”	Care	Python 3 strings are already code points, so indexing is fine. Combining characters and normalisation are the real complications — mention unicodedata.normalize
“Compare two strings ignoring case and punctuation”	Practical fluency	Two pointers with isalnum() skips and lower(), in one pass and $O(1)$ space — no pre-filtered copy needed

Self-check

pch.quizTag Strings — self-check

1. Why is building a string with += in a loop O(n squared)?

   A Because string comparison is slow B Because strings are immutable, so each concatenation copies the entire string — summing to 1 + 2 + ... + n C Because of garbage collection D It is not — it is O(n)
   pch.quizShowAnswer

   B — Because strings are immutable, so each concatenation copies the entire string — summing to 1 + 2 + ... + n — Collect the parts in a list and join once. At n = 100,000 this is the difference between 5 billion character copies and 100,000.

2. How do you reverse a Python string in place?

   A s.reverse() B You cannot — strings are immutable. Convert with list(s), swap with two pointers, then join. The O(n) space is a language cost, not an algorithmic one C s[::-1] does it in place D Using a stack
   pch.quizShowAnswer

   B — You cannot — strings are immutable. Convert with list(s), swap with two pointers, then join. The O(n) space is a language cost, not an algorithmic one — Naming the distinction between a language constraint and an algorithmic one is the point. The algorithm is O(1) space; Python's immutability forces O(n).

3. You claim a character-frequency map is O(1) space. What does that depend on?

   A The string being short B The alphabet being bounded — at most 26 keys for lowercase letters, so the constant is real C Using a Counter rather than a dict D Nothing — maps are always O(1)
   pch.quizShowAnswer

   B — The alphabet being bounded — at most 26 keys for lowercase letters, so the constant is real — For arbitrary Unicode the bound becomes O(min(n, alphabet size)). Stating the precondition rather than assuming it is what makes the claim defensible.

4. For LC 125 Valid Palindrome, ignoring non-alphanumerics, what is the clean approach?

   A Filter the string into a new one, then compare with its reverse B Two pointers that skip non-alphanumeric characters in place, comparing lower() — one pass, O(1) extra space C Sort both halves D Use a regular expression
   pch.quizShowAnswer

   B — Two pointers that skip non-alphanumeric characters in place, comparing lower() — one pass, O(1) extra space — The filtered-copy version is correct but allocates. The two-pointer version with isalnum() skips is one pass and no extra space, which is what the follow-up asks for.

Recall card

• The governing fact — Python strings are immutable. Every modification allocates.
• Never s += ch in a loop — that is $O(n^2)$. Collect into a list and "".join(parts).
• Slicing copies. Pass indices in recursion rather than s[1:].
• In-place algorithms need list(s) first, then join. Say that the $O(n)$ space is a language cost.
• Frequency maps are $O(1)$ space only for a bounded alphabet. State the precondition.
• Useful built-ins — split(), isalnum(), lower(), ord(c) - ord('a') for a 26-slot count array.

Recap

• Strings are immutable — every “change” builds a new string.
• += in a loop is $O(n^2)$ total; collect pieces in a list and "".join(...) once for $O(n)$.
• ord/chr convert between characters and their integer code points.
• Anagram check: compare Counters ($O(n)$) or sorted copies ($O(n \log n)$).
• Palindrome check: two pointers converging from both ends, $O(n)$ time, $O(1)$ extra space.

Next: Stacks and Queues — LIFO and FIFO structures built from a list and a deque.