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).
- Sequential Ranges: Lowercase ('a'-'z'), uppercase ('A'-'Z'), and digits ('0'-'9') have sequential codes. This allows checking ranges (e.g.,
-
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 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 , then join/convert at the end.
Practice Problems
Character Utilities
Two quick ASCII helpers: classify letters and digits, then convert lowercase letters to uppercase.
String Split
Without using a built-in string split method, implement a split(s, c) method, which receives a string s and a character c and splits s at each occurrence of c, returning a list of strings.
String Join
Without using a built-in string join method, implement a join(arr, s) method, which receives an array of strings, arr, and a string, s, and returns a single string consisting of the strings in arr with s in between them.
String Matching
Implement an index_of(s, t) method, which returns the first index where string t appears in string s, or -1 if s does not contain t.