String Basics for Interviews

Intuition

A string is a sequence of characters from some alphabet (lowercase letters, ASCII, digits, DNA bases). Most string questions become easy once you name precisely which kind of piece they are asking about:

• Substring: a contiguous block s[i:j]. A string of length n has n(n + 1)/2 non-empty substrings (by position).
• Subsequence: characters picked in order but not necessarily adjacent ("ace" in "abcde"). There are 2^n of them.
• Prefix / suffix: a substring that starts at the beginning / ends at the end. A proper prefix or suffix is not the whole string.
• Lexicographic order: compare character by character; at the first difference the smaller character wins, and a proper prefix is smaller than the longer string ("ab" < "abc").
• Palindrome: reads the same backwards ("racecar").
• Hamming distance: for equal-length strings, the number of positions where they differ.

The substring/subsequence distinction usually picks the technique: substrings lead to sliding windows, prefix sums, hashing or KMP; subsequences lead to two pointers (one sequence inside another) or DP (LCS, edit distance).

When to use it in interviews / OAs

Every string problem starts here. Ask early:

1. What is the alphabet? "Lowercase English letters only" lets you use arrays of size 26 instead of hash maps.
2. Substring or subsequence? Contiguous or not?
3. Is the comparison case-sensitive? Do spaces and punctuation count (valid palindrome)?
4. How long can the string be? n = 10^5 rules out the O(n^2) center expansion for some variants and every O(n^3) idea.

Template

Palindromes: two pointers and center expansion

from collections import Counter


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


def longest_palindrome(s: str) -> str:
    # expand around each of the 2n - 1 centers (a character or a gap): O(n^2)
    best_lo, best_hi = 0, 0  # half-open interval [lo, hi)
    for center in range(2 * len(s) - 1):
        lo, hi = center // 2, (center + 1) // 2
        while lo >= 0 and hi < len(s) and s[lo] == s[hi]:
            lo, hi = lo - 1, hi + 1
        if hi - lo - 1 > best_hi - best_lo:
            best_lo, best_hi = lo + 1, hi
    return s[best_lo:best_hi]

Subsequence check with two pointers

def is_subsequence(t: str, s: str) -> bool:
    # is t a subsequence of s? match each character of t as early as possible
    i = 0
    for ch in s:
        if i < len(t) and t[i] == ch:
            i += 1
    return i == len(t)

Counting characters

def is_anagram(a: str, b: str) -> bool:
    return len(a) == len(b) and Counter(a) == Counter(b)


def group_anagrams(words: list[str]) -> list[list[str]]:
    groups: dict[tuple[int, ...], list[str]] = {}
    for w in words:
        key = [0] * 26  # assumes lowercase letters; an O(len) key instead of sorting
        for ch in w:
            key[ord(ch) - ord("a")] += 1
        groups.setdefault(tuple(key), []).append(w)
    return list(groups.values())

Building strings and using order

def compress(s: str) -> str:
    # run-length encoding: "aaabcc" -> "a3b1c2"; collect parts, join once
    parts = []
    i = 0
    while i < len(s):
        j = i
        while j < len(s) and s[j] == s[i]:
            j += 1
        parts.append(f"{s[i]}{j - i}")
        i = j
    return "".join(parts)


def longest_common_prefix(words: list[str]) -> str:
    if not words:
        return ""
    lo, hi = min(words), max(words)  # the two lexicographic extremes differ first
    i = 0
    while i < len(lo) and lo[i] == hi[i]:
        i += 1
    return lo[:i]


def hamming(a: str, b: str) -> int:
    return sum(x != y for x, y in zip(a, b))  # requires len(a) == len(b)

The longest_common_prefix trick works because any prefix shared by the smallest and the largest string in sorted order is shared by everything between them.

Complexity

Operation (Python)	Cost
s[i], len(s)	O(1)
s[i:j] (slice)	O(j - i), it copies
a == b, a < b	O(min(len(a), len(b)))
s + t	O(len(s) + len(t)), a new string
"".join(parts)	O(total length)
t in s, s.find(t)	fast in practice, but do not quote a worst-case bound in an interview
hash(s), dict lookup with a string key	O(len(s)) to hash

C++ is similar: s + t builds a new string, s += t appends in amortized O(len(t)), substr copies, and strlen in a loop condition rescans the whole string every iteration.

The templates above: palindrome check O(n), center expansion O(n^2) time and O(1) space, subsequence check O(len(s)), grouping anagrams O(total length).

Common pitfalls

• Concatenating in a loop. res = res + ch copies res every time and can turn linear work into O(n^2). Append to a list and join once.
• Slicing inside loops. s[i:] in a loop is another hidden O(n^2); pass indices instead.
• Substring vs. subsequence mixed up in the problem statement or in your head.
• Inclusive vs. exclusive bounds. Python slices are half-open: s[i:j] has length j - i.
• Strings are immutable in Python (and Java). Convert to a list to edit in place, then join.
• Numbers as strings compare lexicographically: "10" < "9". Compare by length first or convert.
• Edge cases: empty string, a single character, all characters equal, mixed case, non-letter characters.

Interview variations

• Valid palindrome with one deletion. On the first mismatch try skipping the left or the right character and check the rest with two pointers.
• Longest palindromic substring / count palindromic substrings. Center expansion (O(n^2)); Manacher's algorithm is the linear follow-up.
• Is subsequence with many queries. Precompute, for every position and letter, where that letter appears next; each query then costs O(len(t)).
• Group anagrams, find all anagrams in a string. Count arrays as keys; a sliding window of counts for the "find all" version.
• Reverse words, string compression, encode and decode strings. Careful construction with join and length-prefixed encoding.
• Longest common prefix. Vertical scan, or compare the minimum and maximum strings as above; a trie handles many queries.