Strings: building, comparing and counting

Strings are immutable sequences

A string is an ordered sequence of characters, so indexing s[i] is O(1) and len(s) is O(1), just like a list. The big difference is that strings are immutable: you cannot change a character in place. s[0] = "J" raises TypeError: 'str' object does not support item assignment. Every "change" creates a new string, which costs O(n).

For in-place style work, turn the string into a list of characters with list(s), change the list, and join it back with "".join(chars). Both conversions are O(n).

Characters are numbers underneath

Every character has a number called its code point. ord(c) gives the number and chr(n) gives the character back: ord("A") is 65, ord("a") is 97, ord("0") is 48 and chr(97) is "a". The letters a to z have consecutive numbers, so ord(c) − ord("a") turns a lowercase letter into 0 to 25, which is handy for a count array of size 26.

Palindromes: two ends moving inwards

A palindrome reads the same forwards and backwards, like "madam" or "racecar". s == s[::-1] works but builds a reversed copy, O(n) extra space. The two-pointer way compares s[left] with s[right] and moves both inwards: O(n) time and O(1) extra space. Real problems often say "ignore spaces, punctuation and case"; then skip characters that are not letters or digits (str.isalnum()) and compare lowercase.

def is_pal(s):
    left, right = 0, len(s) - 1
    while left < right:
        if s[left] != s[right]:
            return False
        left += 1
        right -= 1
    return True

print(is_pal("racecar"), is_pal("rupee"))   # Output: True False

Anagrams: same letters, same counts

Two words are anagrams if one is a rearrangement of the other, like "listen" and "silent". Sorting both and comparing is simple, O(n log n). Counting is faster: count each character of the first word, subtract for the second, and check all counts are zero. That is O(n) time; the counts take O(k) space, where k is the number of different characters.

from collections import Counter

print(sorted("listen") == sorted("silent"))     # Output: True
print(Counter("listen") == Counter("silent"))   # Output: True
print(Counter("aab"))                           # Output: Counter({'a': 2, 'b': 1})

Building strings and useful methods

As in Module 1, never grow a long string with += in a loop. Collect pieces in a list and join once. Common methods, each O(n) in the length of the string:

A note on Unicode and Hindi text

Python strings are sequences of Unicode code points, not of what you see as letters. "नमस्ते" looks like 3 or 4 letters, but len("नमस्ते") is 6, because the vowel signs and the half-letter mark (virama) are separate code points. Reversing such text code point by code point breaks how it displays. Interview problems usually use plain English letters, but say this if text in Indian languages is involved. In JavaScript, .length counts UTF-16 units, so "नमस्ते".length is also 6, while an emoji such as "😀" has length 2 in JavaScript and 1 in Python.

Common mistakes

• Trying to change a character with s[i] = c. Fix: convert to a list, change it, then join.
• Forgetting to normalise case or skip punctuation in palindrome problems. Fix: use .lower() and .isalnum(), and ask the interviewer what to ignore.
• Checking anagrams by length only, or with sets (sets lose counts: "aab" and "abb" have the same set). Fix: compare full counts.
• Using is to compare strings. Fix: always use == for string values.
• Off-by-one in two pointers, such as while left <= right with extra moves. Fix: while left < right is enough; the middle character of an odd-length string needs no partner.