String Cheatsheet
A string is a sequence of characters. Many tips that apply to Arrays also apply to Strings.
Time complexity
A Strings is an array of characters, so the time complexities of basic string operations will closely resemble that of array operations.
| Operation | Big-O |
|---|---|
| Access | O(1) |
| Search | O(n) |
| Insert | O(n) |
| Remove | O(n) |
Operations involving another String
Here we assume the other string is of length m.
| Operation | Big-O |
|---|---|
| Find substring | O(n.m) |
| Concatenating strings | O(n + m) |
| Slice | O(m) |
| Split (by token) | O(n + m) |
| Strip (remove leading and trailing whitespaces) | O(n) |
Things to look out for during interviews
- Ask about input character set and case sensitivity.
Corner cases
- Empty string
- String with 1 or 2 characters
- String with repeated characters
- Strings with only distinct character