String Manipulation Interview Patterns: Anagrams, Palindromes, and Substring Problems (2025)

String Fundamentals for Interviews

Strings are immutable in Python and Java — concatenating in a loop is O(n^2). Use a list and join() in Python (O(n) total), or StringBuilder in Java. Key operations: hashing (Counter or array of 26 for lowercase English), two pointers (palindrome check, reversal), sliding window (longest substring problems), and sorting (anagram detection). Common mistake: not handling Unicode vs. ASCII — clarify with interviewer. Most interview problems assume lowercase English letters (26 characters) — use an int[26] instead of a hashmap for O(1) access.

Valid Anagram and Group Anagrams

from collections import Counter

def is_anagram(s: str, t: str) -> bool:
    return Counter(s) == Counter(t)
    # O(n) time, O(1) space (bounded alphabet)

def group_anagrams(strs: list[str]) -> list[list[str]]:
    groups = {}
    for s in strs:
        key = tuple(sorted(s))  # or Counter(s) as frozenset
        groups.setdefault(key, []).append(s)
    return list(groups.values())
    # O(n * L log L) where L = average string length

Longest Palindromic Substring (LC 5) — Expand Around Center

def longest_palindrome(s: str) -> str:
    def expand(left: int, right: int) -> str:
        while left >= 0 and right  len(result): result = odd
        if len(even) > len(result): result = even
    return result
# O(n^2) time, O(1) space. Manacher's algorithm is O(n) but overkill for interviews.

Palindrome Partitioning (LC 131)

def partition(s: str) -> list[list[str]]:
    result = []
    def backtrack(start: int, path: list[str]):
        if start == len(s):
            result.append(path[:])
            return
        for end in range(start + 1, len(s) + 1):
            sub = s[start:end]
            if sub == sub[::-1]:  # is palindrome
                path.append(sub)
                backtrack(end, path)
                path.pop()
    backtrack(0, [])
    return result

Encode and Decode Strings (LC 271)

def encode(strs: list[str]) -> str:
    # Format: length#string for each string
    return "".join(f"{len(s)}#{s}" for s in strs)

def decode(s: str) -> list[str]:
    result = []
    i = 0
    while i < len(s):
        j = s.index('#', i)
        length = int(s[i:j])
        result.append(s[j+1:j+1+length])
        i = j + 1 + length
    return result

String Compression and Roman Numerals

# String compression: "aabcccdddd" -> "a2bc3d4"
def compress(chars: list[str]) -> int:
    write = 0
    i = 0
    while i < len(chars):
        char = chars[i]
        count = 0
        while i  1:
            for c in str(count):
                chars[write] = c; write += 1
    return write

# Integer to Roman (LC 12)
def int_to_roman(num: int) -> str:
    vals = [1000,900,500,400,100,90,50,40,10,9,5,4,1]
    syms = ["M","CM","D","CD","C","XC","L","XL","X","IX","V","IV","I"]
    result = ""
    for v, s in zip(vals, syms):
        while num >= v:
            result += s; num -= v
    return result

See also: Meta Interview Prep

See also: Atlassian Interview Prep

See also: LinkedIn Interview Prep