Camelcase Matching

medium two pointers string matching subsequence

Problem

Given a single query string and a pattern string, the query matches the pattern if you can insert only lowercase letters into the pattern so it equals the query. In other words, the pattern's characters must appear in the query in order (as a subsequence), and every query character that is not consumed by the pattern must be lowercase. Return true if the query matches the pattern.

Inputquery = "FooBar", pattern = "FB"

Outputtrue

"FB" + inserting lowercase "oo" and "ar" yields "FooBar"; the uppercase F and B line up in order.

query

pattern

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

function matches(query, pattern) {
  let j = 0;
  for (const c of query) {
    if (j < pattern.length && c === pattern[j]) {
      j++;
    } else if (c >= "A" && c <= "Z") {
      return false;
    }
  }
  return j === pattern.length;
}

class Solution {
    boolean matches(String query, String pattern) {
        int j = 0;
        for (char c : query.toCharArray()) {
            if (j < pattern.length() && c == pattern.charAt(j)) {
                j++;
            } else if (Character.isUpperCase(c)) {
                return false;
            }
        }
        return j == pattern.length();
    }
}

bool matches(string query, string pattern) {
    int j = 0;
    for (char c : query) {
        if (j < (int)pattern.size() && c == pattern[j]) {
            j++;
        } else if (c >= 'A' && c <= 'Z') {
            return false;
        }
    }
    return j == (int)pattern.size();
}

Explanation

A query matches the pattern if you can reach it by inserting only lowercase letters. That means the pattern must appear inside the query in order (as a subsequence), and any leftover query character must be lowercase. A single two-pointer scan checks both rules at once.

We walk the query with one pointer and keep j pointing at the next pattern character we still need. When the current query char equals pattern[j], we consume it and advance j.

If it does not match, there are two cases. A lowercase char is fine — it is just one of the inserted letters, so we skip it. An uppercase char that did not match is illegal, because we can only insert lowercase, so we return false.

At the end the query passes only if j reached the end of the pattern, meaning every pattern character was matched in order.

Example: query FooBar, pattern FB. F matches, o,o are lowercase inserts and skipped, B matches, a,r are skipped. j reaches the end → true.

Time: O(n) Space: O(1)