Strings in DSA: Immutability, Building Strings and Classic Problems

A string is an array of characters, so indexing s[i] is O(1) and scanning it is O(n). The big difference from a list: in Python, strings are immutable. You can never change a string; every "change" builds a new one.

s = "code"
try:
    s[0] = "m"
except TypeError as e:
    print("Error:", e)

t = "m" + s[1:]       # build a new string instead
print(s, t)

Error: 'str' object does not support item assignment
code mode

The concatenation trap#

Because each + creates a new string and copies both parts, building a long string with += in a loop copies the growing result again and again: O(n²) characters copied in total.

This counts the characters each approach copies:

def copies_with_plus(parts):
    result, copied = "", 0
    for p in parts:
        copied += len(result) + len(p)   # a new string of this length is built
        result = result + p
    return copied

def copies_with_join(parts):
    return sum(len(p) for p in parts)    # join copies each part once

parts = ["ab"] * 1000
print(copies_with_plus(parts))
print(copies_with_join(parts))

1001000
2000

Collect the pieces in a list and call "".join(pieces) once. That copies each character once: O(n).

Counting characters#

Many string problems become easy once you count characters with a dictionary or collections.Counter:

from collections import Counter

word = "mississippi"
counts = Counter(word)
print(counts)
print(counts.most_common(2))

Counter({'i': 4, 's': 4, 'p': 2, 'm': 1})
[('i', 4), ('s', 4)]

Anagrams#

Two words are anagrams if they use the same letters the same number of times ("listen" and "silent"). Comparing counts is O(n); sorting both is O(n log n):

from collections import Counter

def is_anagram(a, b):
    return Counter(a) == Counter(b)

print(is_anagram("listen", "silent"))
print(is_anagram("rat", "car"))
print(sorted("listen") == sorted("silent"))

True
False
True

Palindromes#

A palindrome reads the same forwards and backwards. Checking from both ends towards the middle needs no copy:

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

for word in ["racecar", "level", "python"]:
    print(word, is_palindrome(word))

racecar True
level True
python False

s == s[::-1] is shorter and also O(n), but it builds a reversed copy (O(n) extra space). The two-index version uses O(1) space; it is the two pointers pattern.

Common mistakes#

Practice#

from collections import Counter

def first_unique(s):
    counts = Counter(s)
    for i, ch in enumerate(s):
        if counts[ch] == 1:
            return i
    return -1

print(first_unique("leetcode"))
print(first_unique("loveleetcode"))
print(first_unique("aabb"))

0
2
-1

Key takeaway#

Next: the structure behind fast lookups, Hash Tables, Sets and Maps.