String Manipulation

Strings are fundamental in coding interviews. Since they are essentially arrays of characters, many array techniques apply.

Key Concepts

• Character Encoding: Characters map to numeric codes (ASCII and Unicode).

  • Sequential Ranges: Lowercase ('a'-'z'), uppercase ('A'-'Z'), and digits ('0'-'9') have sequential codes. This allows checking ranges (e.g., 'a' <= c <= 'z') without memorizing ASCII values.
  • Conversion: Know your language's functions to convert between char and int (e.g., Python's ord()/chr(), Go's byte conversion).

• Mutability & Performance:

  • In languages like Python, Java, and JavaScript, strings are immutable. Modifying them creates a new string.
  • Performance Trap: Concatenating strings in a loop (s += c) is often $O(n^2)$ because it copies the entire string each time.
  • Solution: Use a Dynamic Array (Python list, JS array) or StringBuilder (Java, Go's strings.Builder) to build strings in $O(n)$, then join/convert at the end.