Skip to content
Tutorials Center
My learning

Topics

Lesson 26 of 225 ยท Strings

Classic String Problems

Solve the classic interview string problems in Python: palindromes, anagrams, reverse words, run-length compression, common prefix, brackets and rotations.

String questions make up a large share of coding interviews, and most of them are variations of a handful of patterns: two pointers from both ends, frequency counting, a single pass with a small state, and clever use of a doubled string. In this lesson you will solve seven classics. For each, we start with the obvious solution, explain its cost, and then improve it where possible.

If you have not yet read Strings in DSA, do that first: it explains why slicing and += cost more than they look and how Counter, ord and join work. We will use all of them here.

Palindromes

A palindrome reads the same forwards and backwards: "level", "noon". The shortest check compares the string with its reverse, which is O(n) time and O(n) space because the reverse is a copy. A two-pointer check compares characters from both ends moving inward and uses O(1) space.

Real inputs usually add rules: ignore case, spaces and punctuation ("A man, a plan, a canal: Panama"). Skip non-alphanumeric characters as the pointers move rather than building a cleaned copy.

Python Palindrome: reverse versus two pointers

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Both are O(n) time; only the two-pointer version is O(1) extra space. An empty string (or one with no letters) counts as a palindrome. For "palindrome after deleting at most one character", run the two-pointer loop and, at the first mismatch, try skipping the left or the right character once. The longest palindromic substring is a separate and harder problem: see Manacher's algorithm.

Anagrams

Two words are anagrams when one is a rearrangement of the other: "listen" and "silent". Equivalent condition: they contain exactly the same characters with the same counts.

  • Sort both and compare: O(n log n) time.
  • Count characters and compare the counts: O(n) time, O(k) space for k distinct characters.

To group a list of words into anagram families, use a canonical key: the sorted letters, or a tuple of 26 counts, in a dictionary.

Python Anagram check and grouping

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Sorting each word of length L costs O(L log L), so grouping N words is O(N * L log L). Using a count tuple as the key makes it O(N * L). A related question, "is this a permutation of that?", is the same problem; "ransom note" asks whether the counts of one string are covered by another.

Reverse the words in a sentence

Given " the sky is blue ", produce "blue is sky the": reverse the order of the words, with single spaces and no extra whitespace. split() without arguments splits on runs of whitespace and drops empties, so the Python solution is short. The in-place version used in C-like languages reverses the whole string and then each word, which you can mimic with a list of characters.

Python Reverse words, two ways

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Both are O(n) time. The reverse-then-reverse-each-word trick also rotates arrays: it is the same idea as the three-reversal rotate in Array Operations.

Compress a string (run-length encoding)

Replace each run of repeated characters with the character and the count: "aaabccdddd" becomes "a3b1c2d4". A common variant returns the original string if the compressed form is not shorter. Scan once, tracking the current character and the length of its run. Collect pieces in a list and join them at the end.

Python Run-length encoding and decoding

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Time O(n), space O(n) for the output. Two traps: the last run must be flushed after the loop, and counts can have several digits when decoding.

Longest common prefix

Given ["flower", "flow", "flight"], the longest common prefix is "fl". There are several ways to find it:

  • Vertical scan: for each column i, check that every word has the same character at i. Stop at the first mismatch. O(S) where S is the total number of characters.
  • Horizontal: shrink a candidate prefix word by word.
  • Sort trick: after sorting, only the first and last strings can differ the most, so compare just those two.
Python Longest common prefix

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The sorted-extremes trick works because the lexicographically smallest and largest strings share exactly the prefix that all strings share. Prefix problems are a natural fit for a trie.

Valid parentheses (a preview)

Is "{[()]}" balanced, while "([)]" is not? The natural tool is a stack: push every opening bracket; on a closing bracket, the top of the stack must be its partner. The string is valid if you never mismatch and the stack ends empty. We study the stack properly in Stacks; here is a first look.

Python Valid parentheses with a list as a stack

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

O(n) time and O(n) space in the worst case (all openers). A single type of bracket needs only a counter, but with several types the order matters, which is exactly what a stack remembers.

Rotation check

Is "waterbottle" a rotation of "erbottlewat"? Brute force: try every rotation, O(nยฒ). The elegant answer: if t is a rotation of s, then t appears as a substring of s + s. Check the lengths are equal first, otherwise "abc" would "match" inside "abcabc" for a shorter or longer t.

TEXT
s     = waterbottle
s + s = waterbottlewaterbottle
t     = erbottlewat      <- found inside, starting at index 3
Python Rotation check with a doubled string

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Python's in on strings is fast in practice (a tuned search); a guaranteed linear worst case needs KMP on s + s.

Complexity at a glance

Problem Brute force Better Extra space
Palindrome reverse and compare, O(n) two pointers, O(n) O(1)
Anagram sort both, O(n log n) count, O(n) O(k)
Reverse words n/a split and join, O(n) O(n)
Compress n/a single pass, O(n) O(n)
Common prefix pairwise compare vertical scan, O(S) O(1)
Valid brackets repeatedly delete pairs, O(nยฒ) stack, O(n) O(n)
Rotation try all, O(nยฒ) t in s + s O(n)

Common mistakes

  • Forgetting the empty string or a single character in palindrome and prefix problems.
  • Ignoring case or punctuation when the problem says to ignore them (or ignoring the opposite!).
  • Not flushing the last run when compressing.
  • Checking lengths too late in anagram and rotation checks. A length check is a cheap early exit and sometimes required for correctness.
  • Using s.replace() in a loop to simulate bracket removal, which is accidentally O(nยฒ).
  • Sorting characters when counting is enough. Counting is O(n); sorting adds a log factor.

Check your understanding

Quick check ยท 5 questions

of 5 answered You scored / 5 ยท perfect!

  1. 1. Which approach checks whether a string is a palindrome using O(1) extra space?

    The two-pointer scan only keeps two indexes. Reversing the string creates a full copy, which costs O(n) space.
  2. 2. What is a good dictionary key for grouping anagrams?

    All anagrams sort to the same string, and different letter multisets sort to different strings.
  3. 3. Why does t in s + s detect that t is a rotation of s (when the lengths match)?

    Rotating by k moves the first k characters to the end, which is exactly the block starting at index k in the doubled string.
  4. 4. In run-length compression, which bug is most common?

    A run is only written when the next character differs, so the last run has no next character and must be flushed after the loop.
  5. 5. For valid parentheses with three bracket types, why is a stack needed rather than three counters?

    Counters would accept '([)]', because each type is balanced in number, but the nesting is wrong. A stack catches it.

Summary

  • Palindromes: compare from both ends with two pointers (O(n) time, O(1) space); skip non-alphanumeric characters as you go.
  • Anagrams: compare character counts (O(n)) or sorted strings (O(n log n)); use the sorted word or a count tuple as a grouping key.
  • Reverse words with split and join, or reverse everything and then each word.
  • Run-length encoding is one pass with a current character and a counter; flush the last run.
  • Longest common prefix: scan column by column and stop at the first mismatch.
  • Brackets need a stack; a rotation test is len(s) == len(t) and t in s + s.

Next: Pattern Matching: Naive and KMP, where you will search for a pattern inside a long text efficiently.