String Manipulation Basics

Strings are everywhere in real programs — usernames, log lines, JSON payloads, DNA sequences, even source code itself — and a huge share of interview and real-world problems boil down to slicing, scanning, or rebuilding a string efficiently. In Python, strings are immutable sequences of Unicode characters, which shapes almost everything about how you should manipulate them: you never edit a string in place, you always build a new one. This lesson covers how strings work under the hood, the core manipulation techniques (indexing, slicing, searching, building, comparing), their time and space costs, and the mistakes that quietly turn an O(n) solution into an O(n squared) one.

Overview / How Strings Work

A Python str is a sequence of Unicode code points, and like any sequence it supports indexing (s[i]), slicing (s[a:b]), iteration, and len(s). What sets strings apart from lists is that they are immutable — once a string object is created, its contents can never be changed. Every operation that looks like it “modifies” a string (s.upper(), s.replace(...), s + other, s[::-1]) actually allocates and returns a brand-new string object, leaving the original untouched.

This has two big consequences worth internalizing. First, you cannot do s[0] = 'X' the way you could with a list — strings simply don’t support item assignment, and Python raises a TypeError if you try (see Common Mistakes below). Second, because every “edit” allocates a new string, chaining or looping many string edits can be far more expensive than it looks. If you concatenate onto a string n times in a loop, each += copies the entire string built so far into a new, slightly larger block of memory. That’s roughly 1 + 2 + 3 + … + n character-copies, which sums to O(n squared) — a classic hidden performance trap. The standard fix is to accumulate pieces in a list (which grows in amortized O(1) per append) and join them into one string at the end with "".join(...), which does a single O(n) pass.

Slicing is central to string work: s[a:b] returns a new string containing the characters from index a up to (but not including) index b, and CPython allocates exactly enough memory for that new string — so a slice of length k costs O(k), not O(1). Negative indices count from the end (s[-1] is the last character), and s[::-1] is the idiomatic way to reverse a string entirely, because a step of -1 walks the sequence backward.

For scanning and matching, Python gives you the in operator and methods like str.find, str.index, str.count, and str.startswith / str.endswith, all of which walk the string looking for a match rather than doing anything magical — treat them as O(n) (or O(n·m) for a pattern of length m) unless you know otherwise. For splitting and rebuilding text, str.split() and str.join() are the two workhorses, and they’re what make the list-then-join pattern above so natural: split a string into pieces, transform the pieces, then join them back.

Time and Space Complexity

The table below summarizes the cost of the operations you’ll use constantly. n is the length of the string (or of the resulting string, for building operations); m is the length of a pattern being searched for.

Operation	Time	Space	Why
s[i] (index)	O(1)	O(1)	Strings are stored as a contiguous array; indexing is direct offset access.
s[a:b] (slice)	O(k)	O(k)	A new string of length k = b – a is allocated and copied.
len(s)	O(1)	O(1)	Python strings cache their length; no scan is needed.
s1 + s2 (single concat)	O(n)	O(n)	Both operands are copied into one new string of combined length.
s += x inside a loop, n times	O(n squared)	O(n)	Each iteration copies the string built so far; costs sum 1+2+…+n.
"".join(parts)	O(n)	O(n)	Total output length is computed once, then filled in a single pass.
x in s / s.find(x)	O(n·m)	O(1)	Worst case scans the text for each possible alignment of the pattern (practically faster due to CPython’s optimizations, but don’t rely on that).
s.split() / s.replace()	O(n)	O(n)	A single pass over the string, building a new string or list output.
s[::-1] (reverse)	O(n)	O(n)	Every character is visited once to build the reversed copy.
sorted(s)	O(n log n)	O(n)	Returns a new sorted list of characters using Timsort.

Examples

The following examples move from a classic two-pointer technique, to frequency counting with the standard library, to building and comparing strings the efficient way.

Example 1: Reversing a String and Checking for a Palindrome

Reversing a string is most idiomatically done with the slice s[::-1] — a step of -1 walks the string from the last index to the first. Checking whether a string is a palindrome doesn’t need to build a reversed copy at all: a two-pointer scan that walks in from both ends and bails out at the first mismatch is both clearer and avoids the O(n) extra memory of a reversed copy.

def reverse_string(s: str) -> str:
    return s[::-1]

def is_palindrome(s: str) -> bool:
    left, right = 0, len(s) - 1
    while left < right:
        if s[left] != s[right]:
            return False
        left += 1
        right -= 1
    return True

word = "level"
print(reverse_string(word))
print(is_palindrome(word))
print(is_palindrome("hello"))

Output:

level
True
False

reverse_string("level") returns the string read backward — which happens to be “level” again, since it’s a palindrome. is_palindrome("level") walks left=0/right=4 (‘l’ == ‘l’), then left=1/right=3 (‘e’ == ‘e’), then stops because left is no longer less than right, so it returns True without ever comparing the middle character. is_palindrome("hello") fails immediately: s[0] is ‘h’ and s[4] is ‘o’, so the function returns False on the very first comparison.

Example 2: Counting Character Frequency

Counting how often each character appears is one of the most common string subroutines in interview problems (anagrams, first unique character, longest substring without repeats). Rather than hand-rolling a dict and checking if key in counts, reach for collections.Counter, which is built exactly for this and reads clearly.

from collections import Counter

def char_frequency(s: str) -> dict[str, int]:
    return dict(Counter(s))

def most_common_char(s: str) -> str:
    counts = Counter(s)
    return counts.most_common(1)[0][0]

text = "programming"
print(char_frequency(text))
print(most_common_char(text))

Output:

{'p': 1, 'r': 2, 'o': 1, 'g': 2, 'a': 1, 'm': 2, 'i': 1, 'n': 1}
r

Counter(text) walks “programming” once, tallying each letter. Because Counter is a dict subclass, printing it (after converting to a plain dict) shows keys in the order they were first seen — p, r, o, g, a, m, i, n — not alphabetical order, and not sorted by count. most_common(1) then sorts by count descending; ‘r’, ‘g’, and ‘m’ are tied at 2 occurrences each, and ties are broken by first-seen order, so ‘r’ — the first of the tied letters to appear in the original string — wins.

Example 3: Building and Comparing Strings Efficiently

This example shows the accumulate-then-join pattern for building output, plus a one-line anagram check using sorted(), which works because two strings are anagrams of each other exactly when they contain the same multiset of characters — and sorting puts that multiset into a canonical, comparable order.

def build_greeting(names: list[str]) -> str:
    parts = []
    for name in names:
        parts.append(f"Hello, {name}!")
    return " ".join(parts)

def is_anagram(word_a: str, word_b: str) -> bool:
    return sorted(word_a.lower()) == sorted(word_b.lower())

names = ["Ada", "Grace"]
print(build_greeting(names))
print(is_anagram("Listen", "Silent"))
print(is_anagram("Hello", "World"))

Output:

Hello, Ada! Hello, Grace!
True
False

build_greeting loops over names, appends a formatted greeting for each into a list, then joins them with a single space in one O(n) pass — never touching += on a string. is_anagram("Listen", "Silent") lowercases both to “listen” and “silent”, sorts each into the same six letters in the same order (e, i, l, n, s, t), and finds them equal, so it returns True. “Hello” and “World” sort to entirely different letters, so the second call returns False.

How It Works Step by Step

Let’s trace is_palindrome("level") from the Example 1 code one step at a time, watching left and right converge.

Step	left	right	s[left]	s[right]	Equal?	Action
1	0	4	‘l’	‘l’	yes	left += 1, right -= 1
2	1	3	‘e’	‘e’	yes	left += 1, right -= 1
3	2	2	—	—	loop exits (left < right is false)	return True

Notice the loop never actually compares index 2 against itself — once left and right meet or cross, there’s nothing left to check, so the function can safely return True. This is exactly why the loop condition is left < right rather than left <= right: the strict inequality is what lets the middle element of an odd-length string skip comparing itself, and forgetting this distinction is one of the more common palindrome-check bugs.

Common Mistakes

Mistake 1: Building a String with += Inside a Loop

It’s tempting to build output the same way you’d build up a running total — starting empty and adding to it in a loop. For strings, though, every += allocates an entirely new string, so doing this n times costs O(n squared), not O(n).

def build_csv_wrong(items: list[str]) -> str:
    result = ""
    for item in items:
        result += item + ","
    return result

data = ["a", "b", "c"]
print(build_csv_wrong(data))

Output:

a,b,c,

This works and prints a,b,c, — the trailing comma aside, the output is even correct. The problem is purely about scale: for a 100-item list this is invisible, but for a 100,000-item list it’s the difference between milliseconds and minutes. The fix is to accumulate pieces in a list and join once at the end, doing the same job in a single O(n) pass:

def build_csv(items: list[str]) -> str:
    return ",".join(items)

data = ["a", "b", "c"]
print(build_csv(data))

Output:

a,b,c

Mistake 2: Off-by-One Errors in Slice Bounds

Slice end indices are exclusive — s[a:b] stops before index b, not at it. It’s easy to subtract one too many (or too few) when translating “the first n characters” into a slice.

def first_n_chars_wrong(s: str, n: int) -> str:
    return s[0:n - 1]

text = "algorithm"
print(first_n_chars_wrong(text, 4))

Output:

alg

The intent was to grab the first 4 characters of “algorithm”, but s[0:n - 1] with n = 4 slices s[0:3], which only grabs 3 characters (“alg”) and silently drops the ‘o’. The fix is to remember that s[0:n] already stops before index n, so no extra -1 is needed:

def first_n_chars(s: str, n: int) -> str:
    return s[0:n]

text = "algorithm"
print(first_n_chars(text, 4))

Output:

algo

Mistake 3: Trying to Mutate a String Like a List

Because strings look and act like sequences in every other way, it’s an easy habit to reach for index assignment the way you would with a list. Strings don’t support it:

name = "james"
name[0] = "J"
print(name)

Output:

TypeError: 'str' object does not support item assignment

There is no way to change one character of a string in place — you always build a new string, typically by slicing around the part you want to change and concatenating (or, for repeated edits, by converting to a list of characters, mutating that, and joining at the end):

def capitalize_first(s: str) -> str:
    if not s:
        return s
    return s[0].upper() + s[1:]

name = "james"
print(capitalize_first(name))

Output:

James

A related, quieter trap is comparing strings with is instead of ==. is checks object identity, not content equality, and while CPython sometimes reuses (“interns”) short string literals in a way that makes a is b appear to work by coincidence, that behavior is an implementation detail, not a language guarantee — always compare string contents with ==.

Best Practices

• Build strings by appending pieces to a list and calling "".join(...) once, instead of looping with += — the difference is O(n) vs O(n squared) on large inputs.
• Use f-strings (f"...") for formatting instead of chained + concatenation; they’re faster and far more readable once more than one value is involved.
• Reach for collections.Counter when you need character or word frequency counts instead of hand-rolling a dict with manual if key in counts checks.
• Remember slice end indices are exclusive: s[a:b] has length b - a. Double-check off-by-one boundaries whenever you translate “first n” or “last n” into a slice.
• Never try to assign into a string index; rebuild the string instead (via slicing, concatenation, or a list-of-characters join).
• Compare strings with ==, never is — string identity/interning is a CPython implementation detail, not a language guarantee.
• For case-insensitive comparisons, call .lower() (or .casefold() for more aggressive Unicode-aware matching) on both sides before comparing.
• When searching for a fixed substring, prefer the built-in in operator or str.find/str.index over writing your own scanning loop — they’re implemented in C and are almost always faster.

Practice Exercises

1. Palindrome Permutation: Write a function that returns True if the letters of a given string (ignoring spaces and case) can be rearranged into some palindrome — for example, “tact coa” should return True because it can be rearranged into “tacocat”. Hint: a string’s letters can form a palindrome if at most one character occurs an odd number of times; try counting letters with Counter and checking how many counts are odd.
2. String Compression: Write a function that compresses a string using run-length counts of repeated characters, e.g. “aaabbcccc” becomes “a3b2c4”. If the compressed string would not be strictly shorter than the original, return the original string unchanged. Hint: walk the string once, tracking the current character and a run length, and flush a (character, count) pair whenever the character changes.
3. Rotation Check: Given two strings s1 and s2 of the same length, write a function that returns True if s2 is a rotation of s1 (for example, “waterbottle” and “erbottlewat”) using only one call to a substring-search method. Hint: every rotation of s1 is a substring of s1 + s1.

Summary

• Python strings are immutable sequences of Unicode characters — every “edit” creates a new string object; none of them modify the original in place.
• Indexing is O(1); slicing and single concatenation cost O(k) in the size of the result; reversing, splitting, and joining are all O(n).
• Concatenating with += inside a loop is O(n squared) overall — accumulate pieces in a list and call "".join() once for O(n).
• Two-pointer scanning (as in a palindrome check) avoids building extra copies and short-circuits on the first mismatch.
• collections.Counter is the standard tool for character/word frequency counting and powers anagram checks, “most common” queries, and more.
• Always compare string contents with ==, never with is, and never attempt index assignment on a string — rebuild it instead.