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 += chunks += chunk in a loop $O(n^2)$ overall.
Why building a list of pieces and calling "".join(...)"".join(...) is $O(n)$ .
ordord/chrchr, 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.

Strings are immutable

Every “modification” of a Python strstr 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)

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))

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}}

`ordord`, `chrchr`, and ASCII

Characters are just small integers under the hood — ordord and chrchr 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'

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

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]s[i]`	$O(1)$
Slice of length $k$	`s[a:b]s[a:b]`	$O(k)$
Concatenation	`s1 + s2s1 + s2`	$O(n + m)$
`+=+=` in a loop, $n$ times	`s += chunks += chunk`	$O(n^2)$ total
`"".join(parts)"".join(parts)`	one call	$O(n)$ total
Search substring	`x in sx in s`	$O(n \cdot m)$ worst case
Length	`len(s)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"))

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"))

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

#	Problem	Difficulty	The twist
242	Valid Anagram	Easy	`Counter(s) == Counter(t)Counter(s) == Counter(t)`, or a 26-slot tally when you must avoid the import
125	Valid Palindrome	Easy	Filter to alphanumerics and lowercase, then close in from both ends
14	Longest Common Prefix	Easy	Compare column by column and stop at the first mismatch — no sorting needed

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^51 <= len(s) <= 10^5, printable ASCII.

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

Editorial

Swap the outermost pair and move inward. while left < rightwhile 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()s.reverse() is the idiomatic in-place answer, and s[::-1]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) <= 2001 <= len(strs) <= 200, 0 <= len(strs[i]) <= 2000 <= len(strs[i]) <= 200, lowercase letters.

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

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"]["ab","a"] giving "a""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 ii 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 ss. 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^41 <= len(s) <= 10^4, letters, digits and spaces, and there is at least one word.

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

Editorial

s.split()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()"a b".split() gives ['a', 'b']['a', 'b'], while "a b".split(" ")"a b".split(" ") gives ['a', '', 'b']['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.

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(...)"".join(...) once for $O(n)$ .
ordord/chrchr convert between characters and their integer code points.
Anagram check: compare CounterCounters ( $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 dequedeque.

If this helped you, consider buying me a coffee ☕

Buy me a coffee

Strings

What you’ll learn

Strings are immutable

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

ordord, chrchr, and ASCII

Slicing and reversal

Complexity of common string operations

Pattern: anagram check

Pattern: palindrome check

LeetCode problem set

Practice — real LeetCode problems

LC 344 — Reverse String · Easy

LC 14 — Longest Common Prefix · Easy

LC 151 — Reverse Words in a String · Medium

Recap

Was this page helpful?

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

`ordord`, `chrchr`, and ASCII