Strings: 8 Practice Problems with Solutions

This post collects eight classic string problems that show up over and over in interviews. Each entry has the problem statement, examples, an approach with Big-O analysis, and a clean Python solution. Type them out yourself — the muscle memory matters more than reading the answer.

1. Valid Anagram

Problem. Given two strings s and t, return True if t is an anagram of s — i.e. they use exactly the same characters with the same multiplicities.

Examples.

s = "anagram", t = "nagaram"   -> True
s = "rat",     t = "car"       -> False

Approach

Compare frequency counts. If the strings are restricted to lowercase ASCII, a fixed-size array of 26 counters runs in O(n) time and O(1) extra space. The lengths must match — a quick early exit.

Time: O(n). Space: O(1) for fixed alphabet, O(k) for general Unicode.

Solution

def is_anagram(s: str, t: str) -> bool:
    if len(s) != len(t):
        return False
    counts = [0] * 26
    for ch in s:
        counts[ord(ch) - ord('a')] += 1
    for ch in t:
        counts[ord(ch) - ord('a')] -= 1
        if counts[ord(ch) - ord('a')] < 0:
            return False
    return True

print(is_anagram("anagram", "nagaram"))   # True
print(is_anagram("rat", "car"))           # False

A one-liner using Counter works too, at the cost of slightly more memory:

from collections import Counter
def is_anagram(s, t):
    return Counter(s) == Counter(t)

2. Reverse String

Problem. Reverse a list of characters in place. You must not allocate a separate array.

Examples.

s = ['h','e','l','l','o']   ->   ['o','l','l','e','h']
s = ['H','a','n','n','a','h'] -> ['h','a','n','n','a','H']

Approach

Two pointers from both ends, swapping until they cross. O(n) time, O(1) extra space.

Solution

def reverse_string(s: list[str]) -> None:
    i, j = 0, len(s) - 1
    while i < j:
        s[i], s[j] = s[j], s[i]
        i += 1
        j -= 1

chars = list("hello")
reverse_string(chars)
print(chars)    # ['o', 'l', 'l', 'e', 'h']

Why the in-place restriction matters: s[::-1] is shorter but allocates an O(n) array. In a system where the input buffer is huge, that doubles your memory.

3. First Unique Character in a String

Problem. Given a string s, return the index of the first character that does not repeat. Return -1 if every character repeats.

Examples.

s = "leetcode"     -> 0    ('l' appears only once)
s = "loveleetcode" -> 2    ('v' appears only once)
s = "aabb"         -> -1

Approach

Two passes. First, count each character’s occurrences. Second, walk the string from the left and return the index of the first character whose count is 1.

Time: O(n). Space: O(1) for ASCII, O(k) for Unicode.

Solution

from collections import Counter

def first_uniq_char(s: str) -> int:
    counts = Counter(s)
    for i, ch in enumerate(s):
        if counts[ch] == 1:
            return i
    return -1

print(first_uniq_char("leetcode"))       # 0
print(first_uniq_char("loveleetcode"))   # 2
print(first_uniq_char("aabb"))           # -1

4. Group Anagrams

Problem. Given a list of strings, group those that are anagrams of one another. Return the groups in any order.

Examples.

strs = ["eat","tea","tan","ate","nat","bat"]
-> [["eat","tea","ate"], ["tan","nat"], ["bat"]]

Approach

Two strings are anagrams iff their sorted character sequences are equal. Use the sorted string as a dictionary key.

Time: O(n · m log m), where n is the number of strings and m is the average length (sorting dominates). Space: O(n · m) for the output.

An alternative key — a 26-tuple of counts — runs in O(n · m) without the log factor:

key = tuple of counts of 'a'..'z' for this word

Solution

from collections import defaultdict

def group_anagrams(strs: list[str]) -> list[list[str]]:
    groups = defaultdict(list)
    for word in strs:
        key = tuple(sorted(word))     # or build a 26-tuple of counts
        groups[key].append(word)
    return list(groups.values())

print(group_anagrams(["eat","tea","tan","ate","nat","bat"]))
# [['eat','tea','ate'], ['tan','nat'], ['bat']]

The count-tuple version, for fixed-alphabet inputs:

def group_anagrams_counts(strs):
    groups = defaultdict(list)
    for word in strs:
        counts = [0] * 26
        for ch in word:
            counts[ord(ch) - ord('a')] += 1
        groups[tuple(counts)].append(word)
    return list(groups.values())

5. Longest Substring Without Repeating Characters

Problem. Given a string s, find the length of the longest substring with no repeated characters.

Examples.

s = "abcabcbb"  -> 3   ("abc")
s = "bbbbb"     -> 1   ("b")
s = "pwwkew"    -> 3   ("wke")

Approach

Classic sliding window. Maintain a window [left, right] containing only unique characters. Track the last seen index of each character in a hash map. When you see a repeat that lies inside the current window, slide left to one past the previous occurrence.

Time: O(n). Each index moves at most once. Space: O(k), where k is the size of the alphabet.

Solution

def length_of_longest_substring(s: str) -> int:
    last_seen = {}
    left = 0
    best = 0
    for right, ch in enumerate(s):
        if ch in last_seen and last_seen[ch] >= left:
            left = last_seen[ch] + 1
        last_seen[ch] = right
        best = max(best, right - left + 1)
    return best

print(length_of_longest_substring("abcabcbb"))   # 3
print(length_of_longest_substring("bbbbb"))      # 1
print(length_of_longest_substring("pwwkew"))     # 3

The check last_seen[ch] >= left is the subtle bit — characters seen earlier than the current window do not force the window to shrink.

6. Longest Palindromic Substring

Problem. Return the longest substring of s that is a palindrome.

Examples.

s = "babad"   -> "bab"   (or "aba")
s = "cbbd"    -> "bb"

Approach

Expand around center. Every palindrome has a center — either a single character (odd length) or a gap between two characters (even length). There are 2n−1 such centers; expand outward from each and track the longest result.

Time: O(n²) — best straightforward approach. Space: O(1).

A linear-time solution exists (Manacher’s algorithm) but is rarely required.

Solution

def longest_palindrome(s: str) -> str:
    if not s:
        return ""

    def expand(left: int, right: int) -> tuple[int, int]:
        while left >= 0 and right < len(s) and s[left] == s[right]:
            left -= 1
            right += 1
        return left + 1, right - 1   # last valid window

    start, end = 0, 0
    for i in range(len(s)):
        l1, r1 = expand(i, i)         # odd-length center
        l2, r2 = expand(i, i + 1)     # even-length center
        if r1 - l1 > end - start:
            start, end = l1, r1
        if r2 - l2 > end - start:
            start, end = l2, r2
    return s[start:end + 1]

print(longest_palindrome("babad"))   # 'bab' or 'aba'
print(longest_palindrome("cbbd"))    # 'bb'

7. Valid Parentheses

Problem. Given a string containing only ()[]{}, return True if the brackets are matched and properly nested.

Examples.

"()"        -> True
"()[]{}"    -> True
"(]"        -> False
"([)]"      -> False
"{[]}"      -> True

Approach

Use a stack. Push opening brackets. For each closing bracket, peek at the top of the stack — if it is the matching opener, pop; otherwise return False. At the end the stack must be empty.

Time: O(n). Space: O(n) for the stack in the worst case.

Solution

def is_valid(s: str) -> bool:
    pairs = {')': '(', ']': '[', '}': '{'}
    stack = []
    for ch in s:
        if ch in "([{":
            stack.append(ch)
        else:
            if not stack or stack[-1] != pairs[ch]:
                return False
            stack.pop()
    return not stack

print(is_valid("()"))         # True
print(is_valid("()[]{}"))     # True
print(is_valid("(]"))         # False
print(is_valid("([)]"))       # False
print(is_valid("{[]}"))       # True

The trick that makes this clean is the pairs dictionary — one lookup per closer, no nested conditionals.

8. Implement strStr() (substring search)

Problem. Given two strings haystack and needle, return the index of the first occurrence of needle in haystack, or -1 if it is not present. Return 0 if needle is empty.

Examples.

haystack = "sadbutsad", needle = "sad"    -> 0
haystack = "leetcode",  needle = "leeto"  -> -1
haystack = "hello",     needle = ""       -> 0

Approach

For interview purposes the naive O(n · m) scan is acceptable. For the optimal answer, use KMP for O(n + m). We will show both.

Naive solution

def str_str_naive(haystack: str, needle: str) -> int:
    if not needle:
        return 0
    n, m = len(haystack), len(needle)
    for i in range(n - m + 1):
        if haystack[i:i + m] == needle:
            return i
    return -1

print(str_str_naive("sadbutsad", "sad"))    # 0
print(str_str_naive("leetcode", "leeto"))   # -1

KMP solution

def build_lps(pattern: str) -> list[int]:
    lps = [0] * len(pattern)
    length, i = 0, 1
    while i < len(pattern):
        if pattern[i] == pattern[length]:
            length += 1
            lps[i] = length
            i += 1
        elif length != 0:
            length = lps[length - 1]
        else:
            lps[i] = 0
            i += 1
    return lps

def str_str_kmp(haystack: str, needle: str) -> int:
    if not needle:
        return 0
    lps = build_lps(needle)
    i = j = 0
    while i < len(haystack):
        if haystack[i] == needle[j]:
            i += 1
            j += 1
            if j == len(needle):
                return i - j
        elif j != 0:
            j = lps[j - 1]
        else:
            i += 1
    return -1

print(str_str_kmp("sadbutsad", "sad"))     # 0
print(str_str_kmp("mississippi", "issip")) # 4

The naive version is fine to submit; mentioning KMP shows you know the optimal bound.

Recap

The patterns that solved these eight problems:

• Two pointers — Reverse String
• Frequency counter — Valid Anagram, First Unique Character
• Hash-map key — Group Anagrams (sorted string or count tuple)
• Sliding window — Longest Substring Without Repeating Characters
• Expand around center — Longest Palindromic Substring
• Stack — Valid Parentheses
• Naive scan or KMP — Implement strStr()

These six patterns cover the majority of string interview questions. If a problem feels unfamiliar, ask which of them fits.

Next steps

The next two posts shift from strings to hashing: how hash functions work, the trade-offs of collision strategies, and a follow-up practice set covering Two Sum, Subarray Sum, and the other classics built on hash maps.

→ Next: Hashing and Hash Maps in DSA

Questions or feedback? Email codeloomdevv@gmail.com.