Python String Problems: Anagrams, Palindromes, Parsing and Unicode

Take two spellings of one name: "Zo\u00eb" and "Zoe\u0308". On screen both render as Zoë, yet Python says they are not equal, and one has length 3 while the other has length 4. Nothing is broken. The first uses a single accented character and the second a plain e followed by a combining mark, and a user can produce either by typing or pasting. Text handling is full of this kind of silent difference, and this lesson mixes the classic string problems with the traps that make them harder in real data than in textbook form.

Strings are immutable sequences

A str supports indexing, slicing and iteration like a list, but you can never change one in place. Methods such as upper() and replace() return a new string, and s += "x" creates a new object and rebinds the name. CPython can sometimes optimise repeated concatenation, but that is an implementation detail; the portable way to build a long string is to collect pieces in a list and call "".join(parts) once. Each slice also copies its characters, so s[1:] inside a loop is a hidden O(n) per iteration, the same kind of cost you saw with list.pop(0) in Data Structures.

Grouping anagrams with a canonical key

A word-game club wants to group the words on a rack that are anagrams of each other. Two words are anagrams exactly when their letters sorted are the same, so the sorted letters make a canonical key, and a defaultdict(list) collects words under it. Using casefold() first makes Silent and listen match.

from collections import defaultdict


def group_anagrams(words):
    groups = defaultdict(list)
    for word in words:
        key = "".join(sorted(word.casefold()))      # same letters -> same key
        groups[key].append(word)
    return list(groups.values())


rack_words = ["listen", "Silent", "enlist", "google", "gogole", "cat", "act", "Tac", "dog"]
for group in group_anagrams(rack_words):
    print(group)

# The key is the whole trick: sorted() returns a list of characters, so join it back
print(sorted("listen"), "".join(sorted("listen")))

['listen', 'Silent', 'enlist']
['google', 'gogole']
['cat', 'act', 'Tac']
['dog']
['e', 'i', 'l', 'n', 's', 't'] eilnst

Sorting each word costs O(k log k) for a word of length k. For a fixed small alphabet, a tuple of 26 letter counts as the key brings that to O(k). Either way, the dict makes the grouping O(total letters) instead of comparing every pair of words.

Palindromes without building a second string

The shortcut s == s[::-1] works for clean input but allocates a reversed copy and fails when spaces and punctuation are present. Two pointers handle both: move inwards from each end, skip anything that is not alphanumeric, and compare the rest ignoring case. The same skeleton also answers the common follow-up, "may delete at most one character".

def is_palindrome_phrase(text):
    """True if text reads the same both ways, ignoring case, spaces and punctuation."""
    left, right = 0, len(text) - 1
    while left < right:
        if not text[left].isalnum():
            left += 1
        elif not text[right].isalnum():
            right -= 1
        else:
            if text[left].casefold() != text[right].casefold():
                return False
            left += 1
            right -= 1
    return True


def almost_palindrome(s):
    """True if deleting at most one character makes s a palindrome."""

    def is_pal(i, j):
        while i < j:
            if s[i] != s[j]:
                return False
            i += 1
            j -= 1
        return True

    i, j = 0, len(s) - 1
    while i < j:
        if s[i] != s[j]:
            return is_pal(i + 1, j) or is_pal(i, j - 1)
        i += 1
        j -= 1
    return True


print(is_palindrome_phrase("Was it a car or a cat I saw?"))
print(is_palindrome_phrase("Ticket 4-4 tekciT"))
print(is_palindrome_phrase(""))
print(almost_palindrome("abca"), almost_palindrome("abcda"))

True
True
True
True False

An empty string counts as a palindrome, which is the usual convention; decide your edge cases before you code, not after the tests fail. almost_palindrome tries both deletions at the first mismatch and needs no more, because after one deletion the rest must match exactly.

Parsing messy lines without crashing

Text arrives in whatever shape people typed. A small invoice reader shows the usual toolkit: skip blanks and comment lines, match each line against a pattern, convert money with Decimal rather than float, and collect errors with line numbers so one bad line does not hide the others.

import re
from decimal import Decimal

LINE = re.compile(r"^(?P<qty>\d+)\s*x\s+(?P<item>.+?)\s*@\s*(?P<price>\d+(?:\.\d{1,2})?)$")


def parse_invoice(lines):
    items, errors = [], []
    for number, raw in enumerate(lines, start=1):
        line = raw.strip()
        if not line or line.startswith("#"):
            continue                              # blank lines and comments
        m = LINE.match(line)
        if not m:
            errors.append(f"line {number}: cannot read {line!r}")
            continue
        qty, price = int(m["qty"]), Decimal(m["price"])
        items.append((m["item"], qty, price, qty * price))
    return items, errors


text = """
# order 5521
2 x Cable tie (pack of 100) @ 3.50
1 x Label printer @ 129
three x Tape @ 2.00
10 x Zip bag, small @ 0.40
"""
items, errors = parse_invoice(text.splitlines())
for name, qty, price, subtotal in items:
    print(f"{name:28} {qty:3} x {price:>7} = {subtotal:>7}")
print("total:", sum(i[3] for i in items))
print(errors)

# partition: split once, keep the rest intact
key, _, value = "ship_to = Pune, MH = 411001".partition("=")
print(repr(key.strip()), repr(value.strip()))

Cable tie (pack of 100)        2 x    3.50 =    7.00
Label printer                  1 x     129 =     129
Zip bag, small                10 x    0.40 =    4.00
total: 140.00
["line 5: cannot read 'three x Tape @ 2.00'"]
'ship_to' 'Pune, MH = 411001'

Line numbers start at 1 for the blank first line produced by the triple-quoted string, so the bad line is reported as line 5. Notice partition("="): unlike split("="), it splits only at the first separator and always returns three parts, so a value that itself contains = survives. Reach for a regular expression when the format has structure, for split or partition when it is delimiter-based, and for a real parser (csv, json, datetime.strptime) whenever one exists.

Unicode and immutability gotchas, run once

import unicodedata

composed = "Zo\u00eb"          # Zoe with e-diaeresis as ONE code point
decomposed = "Zoe\u0308"       # plain e followed by a combining diaeresis
print(ascii(composed), ascii(decomposed), composed == decomposed)
print(len(composed), len(decomposed))
print(unicodedata.normalize("NFC", decomposed) == composed)

smile = "\U0001F600"
print(len(smile), len(smile.encode("utf-8")), len("caf\u00e9".encode("utf-8")))

print("STRASSE".lower() == "stra\u00dfe".lower(), "STRASSE".casefold() == "stra\u00dfe".casefold())

s = "parcel"
try:
    s[0] = "P"
except TypeError as err:
    print("TypeError:", err)
t = s
s += "!"
print(s, t, s is t)

parts = [str(n) for n in range(5)]
print("-".join(parts))

'Zo\xeb' 'Zoe\u0308' False
3 4
True
1 4 5
False True
TypeError: 'str' object does not support item assignment
parcel! parcel False
0-1-2-3-4

Common mistakes

• Comparing user-entered names or tags without normalization. Symptom: a user cannot log in or a duplicate record appears although two values "look identical". Normalize to NFC and use casefold() for caseless matching.
• Building a big string with `+=` in a loop. Symptom: runtime grows faster than the input on large data and varies between Python implementations. Collect pieces and join.
• Splitting on a delimiter that can occur in the value. Symptom: ValueError: too many values to unpack or silently truncated data. Use partition, split(sep, maxsplit) or a real parser.
• Using `float` for money while parsing. Symptom: totals like 0.30000000000000004. Parse into Decimal or integer cents.
• Assuming one character is one byte. Symptom: UnicodeEncodeError on write, or truncated text when cutting a byte string in the middle of a character. Decode and encode explicitly with UTF-8.

How this shows up in real projects and interviews

Real projects spend a lot of time cleaning text: normalising names before a join, parsing log lines and CSV exports, validating identifiers, de-duplicating records that differ only in case or accents. The bugs are rarely algorithmic; they come from assuming ASCII. Interviews use the algorithmic cores, anagram grouping, palindrome checks, "valid parentheses" and parsing numbers from text, and a quick note on case folding or Unicode shows depth without costing time. Before coding, ask the interviewer: are inputs ASCII only, is case significant, and what should an empty string return? The answers change your solution. For the dictionary work in the anagram solution, see Data Structures, and when strings need ordering, see Sorting Algorithms.