String Techniques

A string is a frozen list of characters

Python strings are immutable. s[0] = 'x' is a TypeError, and s += char does not append to s — it allocates a brand new string and copies every character across. Do that inside a loop and you have quietly written an O(n²) algorithm inside what looks like an O(n) one.

def build_slow(characters):
    """O(n^2): each += copies everything accumulated so far."""
    result = ""
    for char in characters:
        result = result + char      # new string allocated every iteration
    return result


def build_fast(characters):
    """O(n): list append is amortized O(1), and join allocates once."""
    pieces = []
    for char in characters:
        pieces.append(char)
    return "".join(pieces)

Pick the representation, and the problem solves itself

Almost every string question on this page is won before you write a loop, by turning the string into the shape that makes the question trivial.

Palindromes grow outward from a middle

A palindrome has a middle. Peel one character off each end of a palindrome and what remains is still a palindrome — so run that backwards: start at a middle and push outward while the two ends match. You never re-verify the part you already grew through, which is the entire saving.

The trap is that there are two kinds of middle. An odd-length palindrome such as racecar is centred on a character. An even-length one such as abba is centred on the gap between two characters. A string of length n therefore has n + (n − 1) = 2n − 1 centers, and a solution that only walks the n character-centers silently misses every even-length answer.

Reversing characters, and reversing words

LC 344 hands you a list of characters rather than a string, precisely because a string could not be reversed in place. Two pointers walk toward each other, swapping as they go — the mechanics live in pattern 02, Two Pointers; what matters here is that the list, not the string, is what makes it possible.

def reverse_string(chars):
    """chars is a list of single characters; reverse it in place."""
    left = 0
    right = len(chars) - 1

    while left < right:
        chars[left], chars[right] = chars[right], chars[left]
        left += 1
        right -= 1

The loop stops at left < right, not <=. With an odd length the two pointers meet on the middle character, which needs no swap; using <= swaps it with itself — harmless here, but the same off-by-one corrupts data in reversal problems that do real work at the meeting point.

LC 151Reverse Words in a String

The whole problem is the whitespace rules: leading and trailing spaces are dropped, and runs of several spaces collapse to one. Bare split() does all three for free. split(" ") does not — it emits empty strings for every extra space.

def reverse_words(s):
    # split() with no argument splits on runs of whitespace and
    # discards leading/trailing blanks -- exactly the spec here.
    words = s.split()
    words.reverse()
    return " ".join(words)

LC 125Valid Palindrome — reversal you never perform

Comparing cleaned == cleaned[::-1] works and is O(n) space. The two-pointer version answers the same question in O(1) space and, more usefully, exits early on the first mismatch.

def is_palindrome(s):
    left = 0
    right = len(s) - 1

    while left < right:
        # Skip anything that isn't a letter or a digit, one side at a time.
        if not s[left].isalnum():
            left += 1
        elif not s[right].isalnum():
            right -= 1
        elif s[left].lower() != s[right].lower():
            return False
        else:
            left += 1
            right -= 1

    return True

Note the elif chain: only one pointer moves per iteration when skipping. Advancing both inside a single if can step a pointer over the character it was supposed to compare.

Two strings are anagrams if they normalize to the same thing

An anagram question is never really about order — it is about multisets of characters. Two strategies: count the characters, or map each string to a single canonical form that all its rearrangements share.

LC 242Valid Anagram — count up, then count down

def is_anagram(s, t):
    # Different lengths can never be anagrams -- cheap early exit.
    if len(s) != len(t):
        return False

    counts = {}
    for char in s:
        counts[char] = counts.get(char, 0) + 1

    for char in t:
        if char not in counts:
            return False        # t has a character s never had
        counts[char] -= 1
        if counts[char] == 0:
            del counts[char]    # keep the dict holding only surpluses

    return len(counts) == 0

Deleting keys that hit zero means the final check is just "is the dict empty". The one-liner Counter(s) == Counter(t) is fine to mention afterwards, but write the loop first — it is what shows you understand the invariant.

LC 49Group Anagrams — the canonical form as a key

Group the words by a value that is identical for every rearrangement. There are two standard keys, and the choice is a genuine tradeoff worth stating out loud in an interview.

def group_anagrams(words):
    """Key = the word's letters in sorted order."""
    groups = {}

    for word in words:
        # sorted() returns a LIST, which is unhashable -- convert it.
        key = tuple(sorted(word))       # "eat" and "tea" both -> ('a','e','t')

        if key not in groups:
            groups[key] = []
        groups[key].append(word)

    return list(groups.values())

def group_anagrams(words):
    """Key = a 26-slot vector of letter counts."""
    groups = {}

    for word in words:
        counts = [0] * 26
        for char in word:
            counts[ord(char) - ord("a")] += 1
        key = tuple(counts)             # tuple so it can be a dict key

        if key not in groups:
            groups[key] = []
        groups[key].append(word)

    return list(groups.values())

The count key is asymptotically better and it is the answer to "can you do it without sorting?". But it is only actually faster for long words: with the typical short inputs, hashing a fixed 26-tuple costs more than sorting five letters, and it hard-codes an alphabet that breaks on uppercase or Unicode. Default to the sorted key for clarity; reach for counts when k is large or sorting is explicitly ruled out.

Length prefixes beat delimiters, always

LC 271 asks you to flatten a list of strings into one string and read it back exactly. The instinct is to join with a separator like #. That is wrong for a reason worth internalising: the payload is allowed to contain your separator. There is no safe character, because the input can be arbitrary.

The fix is to tell the decoder how many characters to take before it takes them. Each chunk becomes <length>#<payload>. The # is now only a marker meaning "the digits end here", so it never has to be absent from the payload — the decoder counts rather than searches.

Recognition signals

• "Palindrome", "reads the same backwards", "symmetric substring" → expand around center
• "Anagram", "same letters rearranged", "group these words" → a canonical form used as a dict key
• "Reverse", "in place", and the input is a character array → two converging pointers
• "Serialize / deserialize a list of strings", "send over a network" → length-prefixed chunks
• Output is assembled character by character → a list of pieces plus one ''.join()
• "Common prefix" across a handful of words → vertical scan, column by column (LC 14)
• "Compare versions", "parse this number" → split, then pad the shorter side with zeros (LC 165)
• "Zigzag", "justify this text", "multiply as strings" → plain simulation; write down the bookkeeping variables first (LC 6, 68, 43)

Three skeletons to have in your fingers

T1Expand around every center

def scan_all_centers(s):
    for center in range(len(s)):
        handle(s, center, center)       # odd-length palindromes
        handle(s, center, center + 1)   # even-length palindromes


def handle(s, left, right):
    while left >= 0 and right < len(s) and s[left] == s[right]:
        # s[left..right] is a palindrome right now -- record it here.
        left -= 1
        right += 1
    # After the loop: the last valid palindrome was s[left + 1 : right].

T2Canonical form as a bucket key

def bucket_by_canonical_form(words):
    groups = {}

    for word in words:
        key = tuple(sorted(word))       # must be hashable, so tuple

        if key not in groups:
            groups[key] = []
        groups[key].append(word)

    return groups

T3Build a string without quadratic copying

def transform(s):
    pieces = []

    for char in s:
        if char.isalpha():
            pieces.append(char.upper())
        else:
            pieces.append("_")

    return "".join(pieces)              # one allocation, at the end

Complexity reference

* bounded by the alphabet size, so constant for a–z.

Where string problems bite back