String Matching & Parsing

Pattern matching fundamentals

The most basic string matching question is: does this pattern appear in this text, and where? Start with the brute force approach because it's often good enough, and knowing when "good enough" is actually good enough is itself an important skill.

Brute force string search slides a window across the text, checking at each position whether the pattern matches. It's O(nm) in the worst case, where n is the text length and m is the pattern length. But for most inputs you'll see in an interview, the average case is much better because mismatches happen early and you skip ahead quickly.

import java.util.ArrayList;
import java.util.List;

public class BruteForceSearch {
    public static List<Integer> bruteForceSearch(String text, String pattern) {
        List<Integer> matches = new ArrayList<>();
        for (int i = 0; i <= text.length() - pattern.length(); i++) {
            if (text.substring(i, i + pattern.length()).equals(pattern)) {
                matches.add(i);
            }
        }
        return matches;
    }
}

It's short, readable, and correct. For a single pattern against a reasonably sized text, this is the right answer. Don't overcomplicate it. The next section covers what to reach for when you're matching against many patterns at once, which is where brute force starts to compound on you.

Trie-based multi-pattern matching

When the problem involves matching against many patterns (autocomplete, dictionary lookup, filtering log lines against a set of known error signatures), a trie is the right data structure. This idea of building a data structure or compiling a pattern beforehand saves us time when we run it many instances, something you'll see repeatedly in string matching.

The trie above holds the words "app", "ant", "top", and "ti". Double-bordered nodes mark the end of a complete word. To check if a string matches, you walk character by character from the root. If you reach a terminal node, you've found a match. If you fall off the trie at any point, the string isn't in your set.

import java.util.HashMap;
import java.util.Map;

class TrieNode {
    Map<Character, TrieNode> children = new HashMap<>();
    boolean isEnd = false;
}

public class Trie {
    private final TrieNode root = new TrieNode();

    public void insert(String word) {
        TrieNode node = root;
        for (char ch : word.toCharArray()) {
            node.children.putIfAbsent(ch, new TrieNode());
            node = node.children.get(ch);
        }
        node.isEnd = true;
    }

    public boolean search(String word) {
        TrieNode node = root;
        for (char ch : word.toCharArray()) {
            if (!node.children.containsKey(ch)) {
                return false;
            }
            node = node.children.get(ch);
        }
        return node.isEnd;
    }

    public boolean startsWith(String prefix) {
        TrieNode node = root;
        for (char ch : prefix.toCharArray()) {
            if (!node.children.containsKey(ch)) {
                return false;
            }
            node = node.children.get(ch);
        }
        return true;
    }
}

In an interview, the trie itself is rarely the whole problem. It's a building block. You might use it inside a log parser to match known patterns, or as the dictionary backing an autocomplete system. The interviewer wants to see that you know when a trie is the right choice and that you can integrate it into a larger system.

Finite state machines

When a problem says "validate this format" or "match strings that follow this pattern," think state machines. A finite state machine (FSM) is just a set of states, a set of transitions between them based on input characters, and one or more accepting states. If you end in an accepting state after processing all input, the string matches.

The FSM above validates decimal numbers. S0 is the start state, S3 (double-bordered) is the accepting state. The machine reads digits, then a dot, then more digits. If it ends in S3, the input is a valid decimal.

In code, state machines are usually just an integer (or enum) tracking the current state and a transition table:

public class FsmDecimal {
    enum State {
        START, INTEGER, DOT, DECIMAL, INVALID
    }

    public static boolean isValidDecimal(String s) {
        State state = State.START;
        for (char ch : s.toCharArray()) {
            switch (state) {
                case START:
                    state = Character.isDigit(ch) ? State.INTEGER : State.INVALID;
                    break;
                case INTEGER:
                    if (Character.isDigit(ch)) state = State.INTEGER;
                    else if (ch == '.') state = State.DOT;
                    else state = State.INVALID;
                    break;
                case DOT:
                    state = Character.isDigit(ch) ? State.DECIMAL : State.INVALID;
                    break;
                case DECIMAL:
                    state = Character.isDigit(ch) ? State.DECIMAL : State.INVALID;
                    break;
                default:
                    break;
            }
            if (state == State.INVALID) return false;
        }
        return state == State.DECIMAL;
    }
}

State machines come up a lot. IP address validation, CSV with quoted fields, simplified glob matching are all state machines in disguise. The tell is when the format has modes that depend on what came before: inside a quoted string vs. outside, integer part vs. decimal part. If you catch yourself wanting to track "where am I right now in the format," that's a state machine.

Regular expressions

Regex is a polarizing topic in interviews. Some people love it, some people avoid it entirely. In AI coding interviews, regex occupies a useful middle ground: it's great for quick extraction and validation of well-defined patterns, but it falls apart once you need state that carries across matches.

Good uses of regex in an interview:

• Extracting timestamps, IPs, or error codes from log lines
• Validating formats like email addresses or version strings (approximately; regex can't fully validate emails but can handle the common cases)
• Splitting structured text into fields
• Quick find-and-replace in template expansion

Bad uses of regex in an interview:

• Parsing nested structures (regex fundamentally can't handle balanced parentheses or nested tags)
• Anything where you need to maintain state across matches (that's a state machine job)
• Multi-line entries where one record spans several lines

import java.util.HashMap;
import java.util.Map;
import java.util.regex.Matcher;
import java.util.regex.Pattern;

public class LogParser {
    private static final Pattern LOG_PATTERN =
        Pattern.compile("(\\d{4}-\\d{2}-\\d{2} \\d{2}:\\d{2}:\\d{2}) \\[(\\w+)] (.+)");

    public static Map<String, String> parseLogLine(String line) {
        Matcher matcher = LOG_PATTERN.matcher(line);
        if (!matcher.matches()) {
            return null;
        }
        Map<String, String> result = new HashMap<>();
        result.put("timestamp", matcher.group(1));
        result.put("level", matcher.group(2));
        result.put("message", matcher.group(3));
        return result;
    }
}

In an AI coding interview, regex is useful for the mechanical parts of a larger problem. If you're building a log analyzer and the first step is extracting structured fields from each line, regex handles that quickly. The AI is also very good at writing regex patterns, often better than most humans. Describe what you want to match in plain English, and the AI will usually produce a working pattern on the first try. Just make sure you test it against edge cases.

Combining the pieces

Real interview problems rarely use just one of these techniques. A log analysis tool might use a state machine to handle multi-line entries (a stack trace spans many lines, a single log entry is one), regex to extract fields from each line, and a trie to classify the extracted error codes against a known list. An IP-address validator might use a state machine for the structure (digits, dots, more digits) and brute force comparison against a deny-list.

The skill the interviewer is evaluating is whether you can look at a problem, identify which parts call for which approach, and wire them together into a working system. That decomposition ("I'll use regex to extract fields per line, a state machine to track which multi-line entry I'm in, and a trie to classify error codes") shows you can take big problems and solve them by combining the important pieces.

Each layer should be independently testable. You can test the regex on a single line, the state machine on a small multi-line input, and the trie lookup on a known and unknown code.

Prompting the AI

The biggest thing to do when prompting on string-matching problems is to separate the layers in your prompt. A log analyzer decomposes into extraction (regex per line) → classification (trie or table lookup) → aggregation. A single prompt that asks for all of it produces tangled code that's hard to debug. Three prompts, one per layer, gives you code you can test in isolation before composing.

Specifics:

• Ask for one layer at a time. "Write the regex that extracts timestamp, level, and message from a single line. Don't worry about the aggregation yet." Once that's working, prompt for the next layer separately. Easily the most important thing to keep yourself from falling into a well that sucks you up for 45 minutes.
• For regex, describe the match in plain English and ask for named groups. "Extract the timestamp, log level, and message from each line. Use named groups." A dense one-liner regex is painful to debug six months later. Named groups read like documentation.
• For state machines, sketch the states first. Either out loud to the interviewer or in comments before the code: "Three states: reading the integer part, reading the decimal part, in an accepting state. Transitions on digits, dots, end of input."
• For tries, just ask. The structure is standard enough that a one-line prompt produces a correct implementation. Spend your time on how you're walking the text against it.

Verifying the AI's code

String-handling code has specific failure modes the AI tends to get wrong:

1. Off-by-one in position tracking. Consuming one character too many or too few is the classic. Common in hand-written matchers and state machine transitions. The fix is usually one index, but finding it requires reading the consume/advance logic carefully.
2. Missing error handling for unexpected input. What happens on empty input? On a line that doesn't match the format? On a character the state machine has no transition for? The happy path almost always works; the unhappy path is where bugs hide.
3. Greedy vs. lazy regex. .* will gobble more than you wanted. If the regex is matching too much, switch to .*? or a more specific character class. The AI often defaults to greedy without noticing.
4. Edge cases at structure boundaries. Empty strings, leading/trailing whitespace, single-character inputs, inputs at the maximum length you'd expect. Run each of these explicitly. The test set the interviewer provides usually doesn't cover them.

The way to verify string-handling code without reading every line is to test incrementally. Build the regex, test it on three inputs. Add the state machine wrapper, test it on a multi-line example. Add the trie lookup, test it on a known and unknown pattern. Each step should produce working code before you move on. This is both good engineering and good interviewing. The interviewer gets to watch you build a verified foundation one piece at a time instead of staring at a wall of unverified code.

For regex specifically: feed it three or four adversarial inputs (empty string, partial match, multiple matches, special characters). If the regex was written by the AI and it's dense, ask it to simplify into named groups before you accept the code.

When to use vs. alternatives

The trap on these problems is reaching for heavy machinery when a simple approach works. Match the tool to the complexity:

• split or find beats regex when the format is fixed and simple. If the problem is "extract the value from key=value lines," split("=", 1) is the right answer, not a regex.
• Regex is the right tool for field extraction in a flat structure: log lines, simple validation patterns, find-and-replace.
• A state machine beats regex when the format has distinct modes that depend on what came before. Inside-a-quoted-string vs. outside, reading-the-integer-part vs. reading-the-decimal-part. State is what regex and ad-hoc string handling don't model cleanly.
• A trie beats repeated regex matches when you're matching against a set of fixed patterns (autocomplete, error-code lookup). One trie walk replaces N regex tests.

Reaching for the heaviest tool you know is a negative signal. Reaching for the right tool, and being able to articulate why, is what the interviewer is grading.

What interviewers expect

A few signals on string-matching problems:

• You decompose before coding. Naming the layers ("regex for line extraction, trie for keyword classification, hash map for aggregation") is the strongest single move you can make. The plan is more important than the code.
• You match the tool to the problem. Reaching for a state machine on a key=value parse is overengineering; reaching for regex on something that needs context tracking across lines is underengineering. Calibration matters.
• You test incrementally. Regex first, state machine wrapper next, trie lookup last. The interviewer wants to see you build a verified foundation, not a wall of unverified code.
• You handle malformed input deliberately. Missing fields, unexpected characters, characters the state machine has no transition for. Industrial-strength error messages aren't required, but acknowledging the malformed-input cases out loud separates strong candidates from weak ones.

Interviewers don't expect you to have built a log analyzer from scratch before. Most candidates haven't. What they expect is that you can look at a format description, understand the structure, and systematically translate it into code, with AI help. The willingness to work through an unfamiliar pattern methodically, rather than panicking or guessing, is one of the strongest signals a candidate can give.

Putting it together

String-matching problems collapse into the same workflow every time. Recognize which sub-pattern applies (or which combination), decompose into layers, prompt the AI for one layer at a time, verify each layer before composing.

The hardest skill is calibration: knowing when split is enough, knowing when regex is the right tool vs. when it'll fight you, knowing when a state machine cleanly handles the modes that ad-hoc string handling won't. Get that calibration right and these problems become some of the cleanest in the AI-enabled format, because the AI is excellent at every individual layer once you've told it what each layer should be.