Camelcase Matching: Two-Pointer String Pattern

Given a list of string queries and a string pattern, return a list of booleans where each entry indicates whether the corresponding query matches the pattern. A query matches the pattern if you can insert lowercase letters into the pattern to make it equal to the query. You cannot insert uppercase letters, and you cannot rearrange existing characters.

This is LeetCode 1023: Camelcase Matching, and it shows up frequently in problems that involve matching against camelCase identifiers. Think of how your IDE autocompletes class names when you type just the capital letters.

A few examples with pattern = "FB":

• "FooBar" returns true. Insert oo after F and ar after B.
• "FooBarTest" returns false. The T is an uppercase letter not in the pattern, so it cannot be inserted.
• "FootBall" returns true. Insert oot after F and all after B.
• "FrameBuffer" returns true. Insert rame after F and uffer after B.
• "ForceFeedBack" returns false. The extra uppercase letters F (second one) and B (the Back portion conflicts) break the match.

Why this problem matters

Camelcase matching is a real-world pattern. Every modern IDE uses it when you type FB and it suggests FooBar, FrameBuffer, or FootBall. The underlying algorithm is a simple two-pointer scan that you can generalize to any pattern matching problem where certain characters can be freely inserted.

It also teaches you to think carefully about what characters are "free" to skip and what characters are mandatory. That distinction between skippable lowercase and mandatory uppercase is the entire crux of the problem.

The key insight

Walk through the query string one character at a time while maintaining a pointer into the pattern. At each character in the query:

1. If it matches the current pattern character, advance both pointers.
2. If it does not match but is lowercase, skip it. Lowercase letters can be freely inserted.
3. If it does not match and is uppercase, the query fails. You cannot insert uppercase letters.

After scanning the entire query, check whether the pattern pointer has reached the end. If it has, every pattern character was consumed in order, and the query is a match.

The solution

def camelMatch(queries, pattern):
    def matches(query, pattern):
        p = 0
        for ch in query:
            if p < len(pattern) and ch == pattern[p]:
                p += 1
            elif ch.isupper():
                return False
        return p == len(pattern)

    return [matches(q, pattern) for q in queries]

The matches helper does the real work. The pointer p tracks how far we have progressed through the pattern. For each character ch in the query, we first check if it matches the next pattern character. If so, we consume it. If not, we check if ch is uppercase. An unmatched uppercase letter is an immediate failure because there is no way to "insert" uppercase letters into the pattern.

At the end, we verify that p reached len(pattern). If the query ran out before the pattern was fully consumed, the match fails.

Visual walkthrough

Let's trace the algorithm matching pattern = "FB" against query = "FooBar". The orange pointer p tracks the pattern, and the green pointer q tracks the query.

Notice the pattern: the query pointer always advances, but the pattern pointer only advances on a match. Lowercase non-matches are silently skipped. The moment we see an uppercase letter that does not match the current pattern character, we would return false, but that never happens in this example.

Complexity analysis

Time: O(n * m) where n is the number of queries and m is the maximum length of a query. Each query is scanned once from left to right. The pattern pointer never backtracks, so each individual match check is O(m).

Space: O(1) extra space per query (just one integer pointer). The output list of booleans is O(n), but that is required by the problem.

The building blocks

1. Subsequence checking with constraints

The core of this problem is a constrained subsequence check. You already know the basic "is subsequence" pattern: walk two pointers in the same direction, one through the candidate and one through the target, advancing the target pointer only on matches. Camelcase matching adds one rule on top: unmatched characters must be lowercase.

def is_subsequence(s, t):
    i = 0
    for ch in t:
        if i < len(s) and ch == s[i]:
            i += 1
    return i == len(s)

Compare that to the matches function above. The only difference is the elif ch.isupper(): return False branch. Once you see it as a modified subsequence check, the solution writes itself.

2. Character classification

The decision at each step depends on two questions: does this character match the pattern, and is it uppercase? Python's str.isupper() handles the second question. In other languages you might compare against ASCII ranges or use a standard library function like Character.isUpperCase() in Java.

The key realization is that you never need to look ahead or backtrack. The greedy approach of matching each pattern character at the earliest opportunity is always optimal, for the same reason it works in Is Subsequence: matching now never prevents you from matching later.

Edge cases

• Empty pattern: Every query matches, because there are no characters to consume. The function returns p == 0 == len(pattern), which is true, as long as the query contains no uppercase letters.

• Query shorter than pattern: The loop finishes before p reaches len(pattern), so we return false.

• All lowercase query with non-empty pattern: If the pattern contains uppercase letters, they will never be matched by a fully lowercase query. Return false.

• Query equals pattern exactly: Every character matches one-to-one, p reaches the end, and we return true.

• Pattern has lowercase letters: The algorithm handles this naturally. Pattern characters like "FoBa" require those exact lowercase letters at the right positions. A query like "FooBar" would fail against pattern "FoBa" because after matching F, o, B, a, the leftover r is lowercase (safe to skip), but you also need to match o exactly at position 1, which means you cannot skip it.

From understanding to recall

Camelcase Matching is a one-trick problem. Once you see it as "Is Subsequence plus an uppercase guard," the code is short and hard to get wrong. But that recognition is the valuable part. The next time you see a problem that asks "can this pattern be embedded inside this string with constraints on what can be inserted," you want that connection to fire instantly.

Write the solution from scratch without looking at this page. If you get stuck on the elif branch or forget the final p == len(pattern) check, those are exactly the details that spaced repetition cements into long-term memory.

Related posts

• Is Subsequence - The foundational two-pointer subsequence check that this problem extends with an uppercase constraint
• Implement Trie - An alternative approach to camelcase matching using trie-based prefix lookups
• Long Pressed Name - Another string matching problem where you allow repeated characters but not new ones

CodeBricks gives you problems like Camelcase Matching broken into atomic building blocks, then schedules them with spaced repetition so the patterns stick. Instead of grinding random problems, you drill the specific techniques that transfer across dozens of interview questions.