Topics

Strings: A Study Guide

A string is a sequence of characters, and for algorithmic purposes it behaves much like an array with one crucial twist: in most languages, including Python, strings are immutable. You cannot change a character in place; every “edit” builds a new string. That immutability quietly turns naive concatenation loops into O(n^2) traps and shapes how you should manipulate strings efficiently.

Why Strings Matter#

String questions are interview staples because they combine array techniques (two pointers, sliding windows) with text-specific ideas (character counting, pattern matching, prefix functions). Palindrome checks, anagram grouping, longest-substring-without-repeats, and substring search all show up regularly. They also test attention to detail: off-by-one errors and Unicode assumptions surface fast.

Key Operations and Their Big-O#

OperationTimeNotes
Index a characterO(1)Like an array access
LengthO(1)Cached
Concatenate two stringsO(n + m)Builds a new string
SliceO(k)Copies k characters
Naive substring searchO(n * m)Text length n, pattern m
KMP / Rabin-Karp searchO(n + m)Linear pattern matching

The concatenation row is the trap: joining n pieces one at a time is O(n^2). Collect pieces in a list and call "".join(pieces) once for O(n).

A Short Example#

Two pointers make a palindrome check clean and O(n):

1def is_palindrome(s):
2    left, right = 0, len(s) - 1
3    while left < right:
4        if s[left] != s[right]:
5            return False
6        left += 1
7        right -= 1
8    return True

Common Pitfalls#

  • Building strings in a loop with +=. Immutable strings make this O(n^2). Use a list and join.
  • Assuming ASCII. A “26-length count array” breaks on Unicode. Prefer a dict or Counter unless the problem guarantees lowercase ASCII.
  • Off-by-one on windows and slices. s[i:j] excludes j; sliding-window bounds are where most string bugs live.
  • Reimplementing search naively. The O(n*m) nested loop passes small tests, then times out. Know KMP or Rabin-Karp for large inputs.

Where the Curriculum Covers This#

In the 60-day challenge: