Strings as arrays

A string is an array of characters. Everything in this station works on strings: indexes, slices, two pointers and windows. The one big difference is that a Python string cannot be changed.

Strings cannot change

s[0] = "X" is an error. Every operation that seems to change a string, such as s + t, s.upper() or s.replace(…), builds a new one. So:

• Building a string piece by piece with += can cost O(n²) (n times n): each step may copy the whole string so far. Collect the pieces in a list and call "".join(parts) once (BIGO-8).
• To change characters in place, turn the string into a list with list(s), change the list, then join it.
• Slices copy. s[1:] is a new string of n − 1 characters.

Characters are numbers

Each character has a number, its code point. ord("a") is 97 and chr(97) is "a". The letters a to z have neighbouring numbers, so ord(ch) - ord("a") turns a lower-case letter into 0 to 25. That makes a list of 26 counts work like a small, fast dictionary:

def is_anagram(s, t):            # same letters, any order
    if len(s) != len(t):
        return False
    count = [0] * 26
    for ch in s:
        count[ord(ch) - ord("a")] += 1
    for ch in t:
        count[ord(ch) - ord("a")] -= 1
    return all(c == 0 for c in count)

This is O(n) time and O(1) extra space, because the list is always 26 long. Sorting both strings and comparing also works, in O(n log n). collections.Counter(s) == Counter(t) is the short Python version, and it works for any characters.

Palindromes

A palindrome reads the same forwards and backwards, like "level". The quick test is s == s[::-1], which builds a reversed copy. Two pointers do it without a copy, and they can skip characters that should be ignored:

def is_palindrome(s):
    lo, hi = 0, len(s) - 1
    while lo < hi:
        if not s[lo].isalnum():
            lo += 1
        elif not s[hi].isalnum():
            hi -= 1
        elif s[lo].lower() != s[hi].lower():
            return False
        else:
            lo += 1
            hi -= 1
    return True

The pointers always close in, so the loop runs at most n times. A practice twist: what if you may delete one character? At the first mismatch, you must delete either s[lo] or s[hi]. Try both, and check the rest with plain two pointers.

Searching inside a string

t in s and s.find(t) look for one string inside another. In the worst case the simple method compares len(t) characters at each of about len(s) places, which is O(n × m). CPython uses a faster method in practice. The STRG station covers methods that guarantee O(n + m), such as KMP and the Z-function.

Now try ARRS-P5, Nearly a palindrome.