Strings — Text as a Data Structure

What is it? #

A string is an array of characters, with one extra rule in most languages: it cannot be changed after it is created.

That immutability is why building a string piece by piece in a loop is slow. Each concatenation creates a brand new string and copies everything so far.

Most string problems reduce to a handful of moves: scan once and count, walk from both ends towards the middle, compare sorted or counted versions, or slide a window across.

Knowing the cost of each operation matters. Slicing copies. Comparing two strings walks them. Searching for a substring is not free.

Think of it like this #

A string is a row of letter tiles glued to a board. Reading any tile is instant. Changing one means building a whole new board — which is fine once, and expensive if you do it ten thousand times in a loop.

Simple example #

Three common tasks: check whether a word reads the same backwards, check whether two words use the same letters, and count character frequencies. Each shows a different standard approach.

Code #

from collections import Counter

# 1. Palindrome — walk from both ends inwards. O(n) time, O(1) extra space
def is_palindrome(text):
    cleaned = [c.lower() for c in text if c.isalnum()]
    left, right = 0, len(cleaned) - 1
    while left < right:
        if cleaned[left] != cleaned[right]:
            return False
        left += 1
        right -= 1
    return True

print(is_palindrome("Never odd or even"))   # True

# 2. Anagram — count characters. O(n) beats sorting's O(n log n)
def is_anagram(a, b):
    return Counter(a.replace(" ", "").lower()) == Counter(b.replace(" ", "").lower())

print(is_anagram("listen", "silent"))       # True

# 3. First non-repeating character — one pass to count, one to find
def first_unique(text):
    counts = Counter(text)
    for index, char in enumerate(text):
        if counts[char] == 1:
            return index
    return -1

print(first_unique("swiss"))                # 1

# Building strings: the slow way and the right way
parts = [f"row-{i}" for i in range(10_000)]

slow = ""
for part in parts:
    slow += part            # copies everything each time — O(n^2) overall

fast = "".join(parts)       # one allocation — O(n)

String operation costs (n = length)

read s[i]             O(1)
slice s[a:b]          O(b - a)   copies
s1 + s2               O(len(s1) + len(s2))
s1 == s2              O(n) worst case
sub in s              O(n * m) naive, faster with better algorithms
s.lower(), s.strip()  O(n), and each returns a new string

How it works #

is_palindrome uses two pointers moving towards each other. Each character is looked at once, so it is O(n), and it needs no extra copy beyond the cleaned list. This two-pointer move is the same idea formalised later in the two-pointers lesson.

is_anagram counts how many of each character appear. Two strings are anagrams exactly when the counts match. Counting is O(n); sorting both strings would also work but costs O(n log n) — same answer, more work.

first_unique needs two passes, and that is fine. Two O(n) passes are still O(n), and two simple passes usually beat one clever pass for readability.

The last block is the performance point. slow += part builds a new string on every iteration and copies everything accumulated so far, which makes the loop quadratic. "".join(parts) works out the total size once and fills a single buffer.

The cost table is worth internalising. In particular, slicing is not free — text[1:] inside a recursive function copies the rest of the string each call, which quietly turns a linear algorithm into a quadratic one.

Real-world use #

Text processing is everywhere: parsing log lines, validating input, generating reports, building URLs and queries, cleaning imported data.

The join-versus-concatenate rule shows up in real code that builds CSV rows, HTML fragments or SQL statements in a loop. It is one of the easiest large speedups available in any language.

Search algorithms matter at scale. A naive substring search is fine for short text; full-text search engines use inverted indexes instead of scanning, which is why searching millions of documents is fast.

Encoding is the other real-world dimension. A character is not always one byte — emoji, accents and non-Latin scripts take more. Anything that slices by byte count rather than character count will eventually cut a character in half.

Common mistakes #

• Building strings with += in a loop instead of collecting parts and joining once.
• Slicing inside recursion, which copies and changes the complexity.
• Comparing user text without normalising case and whitespace first.
• Assuming one character equals one byte. Non-ASCII text breaks that assumption.
• Sorting to compare anagrams when counting is both faster and clearer.

Practice #

Write three functions: one that reverses the words in a sentence without reversing the letters, one that returns the longest word, and one that checks whether two strings are one edit apart (insert, delete or replace a single character). State the Big O of each.