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

OperationCost
Index a characterO(1)
Concatenate a + bO(len a + len b)
Compare two stringsO(n)
Naive substring searchO(n · m)
KMP searchO(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

Longest palindromic substring — expand around centre
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]

Common mistakes

  • Repeated s += c in 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.

  1. Building a string by appending one character at a time, n times, to an immutable string costs:

  2. What is the standard O(n) way to check whether two strings are anagrams?

  3. For lowercase English letters only, the cheapest structure for counting frequencies is:

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.

Stuck on Strings?Ask Orbi for a hint, a fresh explanation or a review of your code.

Ask the tutor