9.9 String Algorithms

Each algorithm below reuses tools already covered in this chapter — slicing, sorted(), Counter, and split()/join() — rather than hand-rolled loops wherever Python already provides the idiom.

Reverse String

Extended slicing (see 9.4 String Indexing and Slicing) does it in one line, no loop required.

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

>>> reverse_string("hello")
'olleh'

Palindrome Check

A palindrome reads the same forwards and backwards. Checking one means normalizing case and stripping non-alphanumeric characters first, then comparing the string to its own reverse.

def is_palindrome(s):
    s = ''.join(c.lower() for c in s if c.isalnum())
    return s == s[::-1]

>>> is_palindrome("A man a plan a canal Panama")
True

Anagram Check

Two strings are anagrams if they contain exactly the same characters in a different order. Sorting both strings’ characters and comparing is a simple, reliable way to check.

def is_anagram(a, b):
    return sorted(a.lower()) == sorted(b.lower())

>>> is_anagram("listen", "silent")
True

Character Frequency

collections.Counter builds a frequency map of every character in a single pass — useful for statistics, compression, and cipher analysis.

from collections import Counter

>>> dict(Counter("mississippi"))
{'m': 1, 'i': 4, 's': 4, 'p': 2}

Remove Duplicate Characters (Order-Preserving)

dict.fromkeys() removes duplicates while preserving first-seen order — a plain set() would not, since sets don’t preserve insertion order.

def remove_duplicates(s):
    return "".join(dict.fromkeys(s))     # dict preserves first-seen order

>>> remove_duplicates("programming")
'progamin'

Word and Character Statistics

split() with no arguments splits on any run of whitespace, so counting the resulting list’s length is the simplest way to count words:

>>> len("the quick brown fox".split())     # word count
4
>>> sum(1 for c in "DevOps".lower() if c in "aeiou")     # vowel count
2

Reversing the order of words (different from reversing characters) means splitting into words, reversing the list, and rejoining:

>>> " ".join("the sky is blue".split()[::-1])
'blue is sky the'

Longest / Shortest Word

max()/min() with key=len finds the “biggest” or “smallest” item by any custom measure, not just length — a pattern that generalizes well beyond strings.

>>> words = "Kubernetes simplifies container orchestration".split()
>>> max(words, key=len), min(words, key=len)
('orchestration', 'simplifies')

First Non-Repeating Character

A classic interview warm-up: find the first character that appears exactly once.

def first_non_repeating(s):
    for c in s:
        if s.count(c) == 1:
            return c
    return None

>>> first_non_repeating("swiss")
'w'

String Compression (Run-Length Encoding)

Collapse runs of repeated characters into char+count pairs, falling back to the original if compression doesn’t actually help.

def compress(s):
    result, i = [], 0
    while i < len(s):
        j = i
        while j < len(s) and s[j] == s[i]:
            j += 1
        result.append(s[i] + str(j - i))
        i = j
    compressed = "".join(result)
    return compressed if len(compressed) < len(s) else s

>>> compress("aaabbbcca")
'a3b3c2a1'

Quick Interview Answer

“Most string algorithm questions reduce to combining a small set of tools rather than hand-rolled character loops: s[::-1] for reversal, comparing a cleaned string to its own reverse for palindromes, sorted() for anagrams, Counter for frequency counting, and dict.fromkeys() for order-preserving deduplication. s.count(c) inside a loop finds the first non-repeating character in O(n²) in the naive form; a Counter pass first makes it O(n) — worth mentioning if performance comes up. Run-length compression is the one genuinely algorithmic pattern here: scan for runs, encode char+count, and fall back to the original if compression doesn’t actually shrink it.”

Common Mistakes

• Using a plain set() to deduplicate characters when order matters — sets don’t preserve insertion order; dict.fromkeys(s) does.
• Writing first_non_repeating with s.count(c) inside the loop for a very long string without realizing it’s O(n²) — a Counter pre-pass makes it O(n).
• Forgetting a palindrome check needs to strip punctuation and normalize case first — "A man, a plan" naively fails a raw s == s[::-1] check.