String

Back to Index

Immutable sequence of characters (in Python). Most string problems reduce to array problems once you know the right representation.

Properties

• Immutable in Python - concatenation in a loop is O(n^2), use "".join(list) instead
• Slicing: O(k) where k = slice length
• Comparison: O(n)

Common Representations

• Character frequency array: freq = [0] * 26 (for lowercase letters)
• Counter: Counter(s) for general frequency map
• Sorted string as key: "".join(sorted(s)) - canonical form for anagram grouping

Common Techniques

• Sliding window for substring problems (Sliding Window)
• Two pointers for palindrome checks (Two Pointers)
• Trie for prefix matching (Trie)
• KMP / Rabin-Karp for pattern matching (rare in interviews)

Useful Built-ins (Python)

s.split()           # split on whitespace
s.strip()           # remove leading/trailing whitespace
s.isalpha()         # all letters
s.isdigit()         # all digits
s.isalnum()         # all letters or digits
ord(c) - ord('a')   # 0-indexed position of letter
chr(ord('a') + i)   # reverse: index to letter
"".join(list)       # O(n) string build from list
s[::-1]             # reverse string

---

Problems Using This Data Structure