Notable pitfalls:

- s[i:j] is O(j - i) because it creates a copy instead of a view

- max(range(n)) is O(n)

- substring search is O(n), which is good, but rfind is O(n m)

- iterative string concatenation (for c in ...: s += c) can be O(n^2) due to string immutability according to footnote 10, although it is O(n) in most cases due to an implementation detail of CPython: https://stackoverflow.com/a/34008199