String Problems That Keep Coming Up in Interviews

Quick Answer

Counting characters solves anagrams and frequency questions. Two pointers solve palindromes. A sliding window with last-seen positions solves substring problems. Recognising which pattern applies is most of the work.

Pattern 1: count the characters

Anagram checking is the canonical case:

from collections import Counter

def is_anagram(a, b):
    return Counter(a) == Counter(b)

print(is_anagram("listen", "silent"))   # True

Sorting both strings and comparing also works and is O(n log n). Counting is O(n) and is the answer to give.

The follow-ups all use the same count. First non-repeating character:

def first_non_repeating(s):
    c = Counter(s)
    for ch in s:
        if c[ch] == 1:
            return ch
    return None

print(first_non_repeating("swiss"))   # w

Two passes: one to count, one to find the first with count 1. The second pass must iterate the string rather than the counter, because you need the original order.

Expect the constraint "assume only lowercase letters", which invites a fixed 26-element array instead of a dictionary. Same idea, and mentioning it shows you thought about space.

Pattern 2: two pointers

def is_palindrome(s):
    s = ''.join(c.lower() for c in s if c.isalnum())
    return s == s[::-1]

print(is_palindrome("A man, a plan, a canal: Panama"))   # True

The cleaning step is where marks are lost, not the comparison. Real palindrome questions almost always specify ignoring case, spaces and punctuation, and candidates who skip that fail the given test case.

s[::-1] is idiomatic Python and uses O(n) extra space. The two-pointer version compares from both ends inward in O(1) space:

def is_palindrome_two_pointer(s):
    i, j = 0, len(s) - 1
    while i < j:
        if s[i] != s[j]:
            return False
        i += 1
        j -= 1
    return True

Say both, and say which you would ship. In Python the slice is clearer; in an interview about space complexity, the pointers are the expected answer.

Pattern 3: sliding window

The most valuable pattern here, because it turns O(n²) into O(n).

def longest_unique(s):
    seen = {}
    best = start = 0
    for i, ch in enumerate(s):
        if ch in seen and seen[ch] >= start:
            start = seen[ch] + 1
        seen[ch] = i
        best = max(best, i - start + 1)
    return best

print(longest_unique("abcabcbb"))   # 3

The window is start to i. When a repeat appears inside the current window, jump start past its previous position. The answer for abcabcbb is 3 — abc.

The condition that matters is seen[ch] >= start. Without it, a character last seen before the window wrongly moves the start backwards, and the result is too small. This is the single most common bug in this problem, and it only shows on inputs like abba.

The Python-specific trap: strings are immutable

This costs people performance marks without them noticing.

# O(n^2) -- builds a new string every iteration
result = ""
for ch in text:
    result += ch

# O(n) -- build a list, join once
parts = []
for ch in text:
    parts.append(ch)
result = "".join(parts)

Because strings cannot be modified, += allocates a new string and copies everything each time. Over n characters that is quadratic. Building a list and joining once is linear.

The same reasoning explains why reversing, slicing and replacing all produce new strings rather than modifying in place — and why a function "modifying" a string cannot affect the caller's variable.

What to do when you get a string question

A short routine that covers most of them:

• Ask about the character set. Lowercase only? Unicode? It changes whether a fixed array is acceptable.
• Ask about case and punctuation. Most palindrome and anagram questions hinge on it.
• Check the empty string and single character. Both are palindromes; both break naive index arithmetic.
• Say the pattern out loud. "This looks like a sliding window because we need the longest substring satisfying a property." That sentence is worth more than the code.
• State the complexity before writing, and confirm it after.

The problems worth practising beyond these four: group anagrams, valid parentheses (a stack), longest common prefix, string compression, and longest palindromic substring. Between them they reuse every pattern above. See the time complexity cheat sheet for describing them precisely.

Frequently Asked Questions