Back to Topics
Strings
Strings are sequences of characters — effectively arrays of chars. Most languages treat them as immutable, which means every concatenation creates a new allocation. Mastering string manipulation requires understanding character encoding, frequency counting, and pattern matching.
Key Ideas
- Strings are immutable in Python and Java — use a list/StringBuilder to build in O(n)
- Character frequency maps (hash maps) reduce many O(n²) problems to O(n)
- Sliding window handles longest/shortest substring problems with constraints
- Two-pointer palindrome checks run in O(n) without extra space
- ASCII has 128 characters; a fixed-size frequency array of size 128 is O(1) space
- Lexicographic comparison compares character by character left-to-right
Complexity
| Operation | Time | Space |
|---|---|---|
| Access by index | O(1) | O(1) |
| Search (contains) | O(n·m) | O(1) |
| Concatenation | O(n) | O(n) |
| Substring | O(k) | O(k) |
| Reverse | O(n) | O(n) |
Common Patterns
Frequency MapCount character occurrences in O(n) using a hash map or array of size 26/128.
Sliding WindowTrack a variable-length window to find substrings satisfying a constraint.
Two PointersExpand from centre or converge from ends to check palindromes.
TriePrefix tree for efficient prefix search, autocomplete, and word grouping.
Code Example
Check if two strings are anagramspython
from collections import Counter
def is_anagram(s: str, t: str) -> bool:
if len(s) != len(t):
return False
return Counter(s) == Counter(t)
# Alternative — O(1) space with array of 26
def is_anagram_v2(s: str, t: str) -> bool:
if len(s) != len(t):
return False
count = [0] * 26
for a, b in zip(s, t):
count[ord(a) - ord('a')] += 1
count[ord(b) - ord('a')] -= 1
return all(c == 0 for c in count)💡
Before building a complex solution, ask: can a frequency map reduce this to O(n)?