Overview
A string is an array of characters, so everything from the Arrays topic applies — but strings bring their own habits. In Python and Java they are immutable, so building one character at a time with + quietly turns an O(n) loop into O(n²). The fix is to collect pieces in a list or StringBuilder and join once.
Interview string problems cluster into a few families: counting characters (anagrams), checking symmetry (palindromes), comparing prefixes, and searching for a pattern inside a text. Each family has a standard technique, and recognising the family is most of the work.
Key concepts
Tick a concept once you can explain it in your own words without notes.
Complexity cheat sheet
| Operation | Cost |
|---|---|
| Index a character | O(1) |
| Concatenate a + b | O(len a + len b) |
| Compare two strings | O(n) |
| Naive substring search | O(n · m) |
| KMP search | O(n + m) |
Patterns to recognise
Count and compare
Use it for: Anagrams, permutations, ransom-note style questions.
Build frequency arrays and compare them, or increment for one string and decrement for the other.
Expand around centre
Use it for: Longest palindromic substring, counting palindromes.
Treat each index (and each gap) as a centre and expand while characters match — O(n²) time, O(1) space.
Canonical key
Use it for: Group strings that are "the same" under some transformation.
Map each string to a key (sorted letters, count tuple) and group by key in a hash map.
Code template
def longest_palindrome(s):
start, end = 0, 0
def expand(left, right):
while left >= 0 and right < len(s) and s[left] == s[right]:
left -= 1
right += 1
return left + 1, right - 1
for i in range(len(s)):
for lo, hi in (expand(i, i), expand(i, i + 1)):
if hi - lo > end - start:
start, end = lo, hi
return s[start:end + 1]
string longestPalindrome(const string& s) {
int n = s.size(), start = 0, best = n ? 1 : 0;
auto expand = [&](int l, int r) {
while (l >= 0 && r < n && s[l] == s[r]) { --l; ++r; }
if (r - l - 1 > best) { best = r - l - 1; start = l + 1; }
};
for (int i = 0; i < n; ++i) { expand(i, i); expand(i, i + 1); }
return s.substr(start, best);
}
Common mistakes
- Repeated
s += cin a loop is O(n²) in languages with immutable strings. - Read the problem for case sensitivity and whether to ignore spaces or punctuation.
- Python slices exclude the end index; C++
substr(pos, len)takes a length, not an end.
Quick check
Three questions on Strings. Get all three right to earn +15 XP.
-
Building a string by appending one character at a time, n times, to an immutable string costs:
Each append copies the whole string so far. Collect the pieces in a list and join once instead.
-
What is the standard O(n) way to check whether two strings are anagrams?
Anagrams use exactly the same characters the same number of times.
-
For lowercase English letters only, the cheapest structure for counting frequencies is:
Index with ord(c) - ord('a'): constant-time updates and no hashing overhead.
Challenges
Ordered from easiest to hardest. Solve them on LeetCode, then tick them off here. Know every concept and solve 3 to clear the level.
- Valid AnagramLeetCode Easy +20
- Valid PalindromeLeetCode Easy +20
- Longest Common PrefixLeetCode Easy +20
- Find the Index of the First Occurrence in a StringLeetCode Easy +20
- Group AnagramsLeetCode Medium +40
- Longest Palindromic SubstringLeetCode Medium +40
- String to Integer (atoi)LeetCode Medium +40
- Shortest PalindromeLeetCode Hard +70
Stuck on Strings?Ask Orbi for a hint, a fresh explanation or a review of your code.
Ask the tutor