String Algorithms and Pattern Matching Questions

Covers algorithmic techniques and practical skills for solving string problems and pattern matching tasks. Core algorithm knowledge includes substring search and pattern matching algorithms such as Knuth Morris Pratt, Rabin Karp, Boyer Moore, Z algorithm, Aho Corasick for multiple pattern matching, and rolling hash methods. Data structures and suffix structures are important, including tries, suffix arrays, suffix trees, and suffix automata, together with longest common prefix arrays and related construction techniques. Also includes dynamic programming approaches for string problems such as edit distance and longest common subsequence, palindrome and anagram detection methods, and regular expression concepts and engine behavior. Emphasizes algorithmic complexity analysis, time and space trade offs, memory and streaming constraints, and optimization strategies for very long inputs and high throughput text processing. Practical considerations include parsing and string manipulation idioms in common languages, Unicode and character encoding issues, edge case handling, test case design for strings, and real world applications such as log analysis, text search, and data transformation.

MediumTechnical

48 practiced

Implement Levenshtein edit distance in Java using only O(min(n, m)) space by keeping two rows of the DP table (rolling rows). Signature: int editDistance(String a, String b). Explain when this optimization is applicable and how you would reconstruct the actual edit sequence if required.

Sample Answer

Approach:Use classic DP for Levenshtein distance but keep only two rows (previous and current) of length min(n,m)+1. To minimize space, iterate over the shorter string as columns. This yields O(min(n,m)) space and O(n*m) time.

Code (Java):

java

public class EditDistance {
    public static int editDistance(String a, String b) {
        if (a == null || b == null) throw new IllegalArgumentException("null input");
        // ensure b is the shorter string to use O(min(n,m)) space
        if (a.length() < b.length()) {
            String tmp = a; a = b; b = tmp;
        }
        int n = a.length(), m = b.length();
        // prev and curr of length m+1
        int[] prev = new int[m + 1];
        int[] curr = new int[m + 1];

        // base: transform empty prefix of a to prefixes of b
        for (int j = 0; j <= m; j++) prev[j] = j;

        for (int i = 1; i <= n; i++) {
            curr[0] = i; // cost of deleting i chars from a to match empty b
            char ca = a.charAt(i - 1);
            for (int j = 1; j <= m; j++) {
                int cost = (ca == b.charAt(j - 1)) ? 0 : 1;
                // substitution, insertion, deletion
                curr[j] = Math.min(
                    Math.min(prev[j - 1] + cost, // substitute/match
                             prev[j] + 1),       // delete from a
                    curr[j - 1] + 1               // insert into a
                );
            }
            // swap rows
            int[] tmp = prev; prev = curr; curr = tmp;
        }
        return prev[m];
    }
}

Key points:- Time: O(n*m). Space: O(min(n,m)).- Ensure you iterate columns over the shorter string to minimize row length.- Edge cases: null inputs, empty strings, identical strings, large strings (watch integer overflow if tracking cost beyond int range).

Reconstructing the edit sequence:Keeping only two rows loses backpointers. Options:1) If you need the sequence, run full DP table (O(n*m) space) and backtrack.2) Use Hirschberg’s algorithm: a divide-and-conquer variant that computes split points with two-row DP and recursively reconstructs the alignment in O(n*m) time and O(min(n,m)) space.3) Store checkpoints (partial backpointers) at intervals if approximate memory/time trade-offs are acceptable.

Use Hirschberg when you must reconstruct the edits but still want linear space.

MediumTechnical

76 practiced

Implement Manacher's algorithm in Python to find the longest palindromic substring in linear time. Function signature: def longest_palindrome(s: str) -> str. Explain the transformed string trick (inserting separators) and how the radius array and mirror property are used to avoid re-computation.

Sample Answer

To solve this in linear time, use Manacher's algorithm: transform the string by inserting separators to make all palindromes odd-length, then maintain an array of palindrome radii and a center/right boundary to reuse previously computed information via the mirror property.

python

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

    # Transform: add separators to handle even-length palindromes uniformly
    # Example: "abba" -> "^#a#b#b#a#$" (guards ^ and $ avoid bounds checks)
    T = "^#" + "#".join(s) + "#$"
    n = len(T)
    P = [0] * n  # radius array: P[i] = half-length of palindrome around T[i]
    center = 0
    right = 0

    for i in range(1, n - 1):
        mir = 2 * center - i  # mirror position of i around center

        # If i is within current right boundary, initialize P[i] with mirror or distance to right
        if i < right:
            P[i] = min(right - i, P[mir])

        # Attempt to expand palindrome centered at i
        while T[i + 1 + P[i]] == T[i - 1 - P[i]]:
            P[i] += 1

        # If expanded past right, update center and right
        if i + P[i] > right:
            center = i
            right = i + P[i]

    # Find max radius and its center
    max_len, center_index = max((val, idx) for idx, val in enumerate(P))
    # Map back to original string indices: start = (center_index - max_len - 1)//2
    start = (center_index - max_len) // 2
    return s[start:start + max_len]

Key ideas:- Transformed string (with separators) converts even palindromes to odd ones so expansion logic is uniform.- P stores the radius (number of matched character pairs) at each center in T.- Mirror property: for i within current right boundary, P[i] is at least min(P[mirror], right - i). This avoids re-checking known matched spans.- Expansions only happen when necessary, yielding O(n) time. Space is O(n) for transformed string and P.

Complexity: Time O(n), Space O(n).Edge cases: empty string, all identical chars, single character input.

MediumTechnical

57 practiced

Implement the KMP string search algorithm in Python: def kmp_search(text: str, pattern: str) -> List[int]. Return all starting indices where the pattern appears in the text in O(n+m) time. Include computation of the prefix-function, handle empty-pattern behavior, and explain complexity.

Sample Answer

To solve this, we compute the prefix-function (also called "pi" or LPS) for the pattern in O(m), then scan the text using that pi to find matches in O(n). If pattern is empty, return all starting indices 0..len(text) (common convention).

python

from typing import List

def compute_prefix(pattern: str) -> List[int]:
    m = len(pattern)
    pi = [0] * m
    j = 0  # length of current matched prefix
    for i in range(1, m):
        while j > 0 and pattern[i] != pattern[j]:
            j = pi[j - 1]
        if pattern[i] == pattern[j]:
            j += 1
            pi[i] = j
    return pi

def kmp_search(text: str, pattern: str) -> List[int]:
    n, m = len(text), len(pattern)
    if m == 0:
        # By convention: empty pattern matches at every position 0..n
        return list(range(n + 1))
    pi = compute_prefix(pattern)
    res = []
    j = 0  # current length matched in pattern
    for i in range(n):
        while j > 0 and text[i] != pattern[j]:
            j = pi[j - 1]
        if text[i] == pattern[j]:
            j += 1
            if j == m:
                res.append(i - m + 1)
                j = pi[j - 1]
    return res

Key points:- compute_prefix builds longest proper prefix-suffix lengths to know how far to fall back on mismatch.- Main loop never backtracks in text; j moves via pi, so time is O(n + m).Time complexity: O(n + m). Space: O(m) for pi plus O(k) for result (k = number of matches).Edge cases: empty pattern (handled), pattern longer than text (returns []), overlapping matches (handled, e.g., pattern "aa" in "aaa" -> [0,1]).Alternative: Rolling-hash (Rabin–Karp) gives average O(n+m) but has collision concerns; brute force is O(n*m).

EasyTechnical

49 practiced

Explain Unicode normalization forms (NFC, NFD, NFKC, NFKD) and why normalization matters for reliable string matching across data sources. Describe how you would design ingestion pipelines to normalize user-generated text for search and matching purposes.

Sample Answer

Unicode defines multiple normalization forms to produce consistent binary representations of the same human-readable text:

- NFC (Normalization Form C): Canonical Decomposition followed by Canonical Composition. It composes characters when possible (e.g., "e" + acute combining -> "é" single code point).- NFD: Canonical Decomposition only. It expands composed characters into base + combining marks.- NFKC / NFKD: Same as NFC/NFD but apply compatibility decomposition first — they fold compatibility variants like superscripts, Roman numerals, or fullwidth forms into their compatible equivalents (e.g., "①" → "1").

Why it matters:- Visual/equivalent characters can have different code point sequences; without normalization, equality checks, hashing, deduplication, or search can fail. Normalization ensures consistent bytes for reliable matching across data sources, languages, and input methods.

Designing ingestion pipelines for search/matching:1. Requirements: decide whether to preserve presentation (use NFC) or aggressively fold variants (use NFKC) — e.g., user-facing display vs. identity matching.2. Steps: - Unicode normalization (choose NFC or NFKC based on policy). - Case folding (Unicode-aware, e.g., full casefold) for case-insensitive search. - Strip or normalize whitespace (trim, collapse), and normalize Unicode punctuation if needed. - Remove/control-control characters and normalize emoji/zero-width joiners depending on use case. - Tokenize with Unicode-aware tokenizer and apply stemming/lemmatization as appropriate. - Store both original and normalized forms (keep provenance), and index normalized fields for search/matching.3. Implementation notes: - Use standard libraries (Python: unicodedata.normalize and .casefold; Java: java.text.Normalizer). - Run normalization early and consistently; include tests with examples (composed vs decomposed, fullwidth digits, accented variants). - Be careful with NFKC for user-facing data because it may change semantics (ligatures, unit symbols).

This approach ensures predictable matching while preserving originals for display and audit.

HardTechnical

46 practiced

Implement an Eertree (palindromic tree) in Java or C++ that enumerates all distinct palindromic substrings of a string s in O(n) time and counts the number of occurrences of each palindrome. Provide methods to build the tree and return counts for each distinct palindrome.

Sample Answer

Approach: Use an Eertree (palindromic tree) with two root nodes (length -1 and 0). Process characters left-to-right, find the largest suffix-palindrome that can be extended, create new node when a new palindrome appears, and track occurrence counts. After building, propagate occurrence counts from longer palindromes to their suffix links to get total occurrences.

cpp

#include <bits/stdc++.h>
using namespace std;

struct Node {
    int len;                     // palindrome length
    int link;                    // suffix link (largest proper palindromic suffix)
    array<int,26> next{};        // transitions by char
    long long occ = 0;           // occurrences as end positions
    int firstPos = -1;           // optional: end position of first occurrence
    Node(int l=0): len(l), link(0) { next.fill(0); }
};

struct Eertree {
    string s;
    vector<Node> tree;
    int last; // node representing largest suffix-palindrome of processed prefix
    Eertree(int n=0) {
        tree.reserve(n+5);
        tree.push_back(Node(-1)); // 0: root with len -1
        tree.push_back(Node(0));  // 1: root with len 0
        tree[0].link = 0;
        tree[1].link = 0;
        last = 1;
    }
    void build(const string &str) {
        s = str;
        for (int i = 0; i < (int)s.size(); ++i) addChar(i);
        // propagate occurrences: iterate nodes by decreasing length
        vector<int> idx(tree.size());
        iota(idx.begin(), idx.end(), 0);
        sort(idx.begin(), idx.end(), [&](int a,int b){ return tree[a].len > tree[b].len; });
        for (int id : idx) if (id>1) tree[tree[id].link].occ += tree[id].occ;
    }
    void addChar(int pos) {
        int cur = last;
        int c = s[pos]-'a';
        while (true) {
            int curlen = tree[cur].len;
            if (pos-1-curlen >= 0 && s[pos-1-curlen]==s[pos]) break;
            cur = tree[cur].link;
        }
        if (tree[cur].next[c]) {
            last = tree[cur].next[c];
            tree[last].occ++;
            return;
        }
        // create new node
        Node node(tree[cur].len + 2);
        tree.push_back(node);
        int newNode = tree.size()-1;
        tree[cur].next[c] = newNode;
        tree[newNode].occ = 1;
        tree[newNode].firstPos = pos;
        if (tree[newNode].len == 1) {
            tree[newNode].link = 1;
            last = newNode;
            return;
        }
        // find suffix link for new node
        int linkCandidate = tree[cur].link;
        while (true) {
            int candidLen = tree[linkCandidate].len;
            if (pos-1-candidLen >=0 && s[pos-1-candidLen]==s[pos]) break;
            linkCandidate = tree[linkCandidate].link;
        }
        tree[newNode].link = tree[linkCandidate].next[c];
        last = newNode;
    }
    // Return vector of pairs (palindrome_string, count)
    vector<pair<string,long long>> getPalindromes() {
        vector<pair<string,long long>> res;
        for (int i = 2; i < (int)tree.size(); ++i) {
            int len = tree[i].len;
            int endPos = tree[i].firstPos;
            string p = s.substr(endPos - len + 1, len);
            res.emplace_back(p, tree[i].occ);
        }
        return res;
    }
};

Key points:- Build is O(n) since each character walks suffix links amortized constant and creates ≤ n nodes.- Space O(n) nodes; each node has 26 transitions (or use map for sparse alphabets).- Edge cases: empty string (returns empty list), non-lowercase input (adapt alphabet), large alphabet (use unordered_map<char,int> per node).- Alternative: Manacher finds palindromic radii but doesn't enumerate distinct palindromes with counts as directly.

Unlock Full Question Bank

Get access to hundreds of String Algorithms and Pattern Matching interview questions and detailed answers.

Join thousands of developers preparing for their dream job.