Camelcase Matching - Practice Coding Problems

Camelcase Matching - Problem

Given an array of strings queries and a string pattern, return a boolean array answer where answer[i] is true if queries[i] matches pattern, and false otherwise.

A query word queries[i] matches pattern if you can insert lowercase English letters into the pattern so that it equals the query. You may insert a character at any position in pattern or you may choose not to insert any characters at all.

Input & Output

Example 1 — Basic Matching

$ Input: queries = ["ForceFeedBack","ForYou","Fun"], pattern = "FB"

› Output: [true,false,false]

💡 Note: ForceFeedBack can be formed by inserting lowercase letters into FB (F+orce+B+ack). ForYou cannot because it has Y (uppercase) not in pattern. Fun cannot because it lacks B.

Example 2 — Exact Match

$ Input: queries = ["CompetitiveProgramming","FaceBook"], pattern = "CamelCase"

› Output: [false,false]

💡 Note: CompetitiveProgramming has P (uppercase) not in pattern. FaceBook has uppercase letters F,B that don't match pattern CamelCase.

Example 3 — Edge Case

$ Input: queries = ["AA","aaa"], pattern = "AAA"

› Output: [false,false]

💡 Note: AA is missing one A from pattern AAA. aaa has all lowercase but pattern requires uppercase A's.

Constraints

1 ≤ queries.length ≤ 100
1 ≤ queries[i].length ≤ 100
1 ≤ pattern.length ≤ 100
queries[i] and pattern consist of English letters

Visualization

Tap to expand

Understanding the Visualization

Input

Array of query strings and a pattern string

Process

Check if each query can be formed by inserting lowercase letters into pattern

Output

Boolean array indicating which queries match

Key Takeaway

🎯 Key Insight: Uppercase letters form the skeleton that must match exactly, while lowercase letters are just filler that can be inserted anywhere

Asked in

G Google 35 f Facebook 28 a Amazon 22 M Microsoft 18

The key insight is that uppercase letters must match exactly in sequence, while lowercase letters can be inserted anywhere. Best approach uses two pointers to scan through query and pattern simultaneously. Time: O(n × m), Space: O(1)

Common Approaches

Approach	Time	Space	Notes
✓ Two Pointers Optimization	O(n * m)	O(1)	Use two pointers to efficiently match pattern with query
Brute Force Character Matching	O(n * m * k)	O(1)	For each query, try to match characters one by one with the pattern

Two Pointers Optimization — Algorithm Steps

Initialize two pointers for pattern and query
Match characters: advance both if equal, advance query only for lowercase
Reject if uppercase letter doesn't match
Check if entire pattern is consumed

Visualization

Tap to expand

Step-by-Step Walkthrough

Initialize Pointers

Set i=0 for query, j=0 for pattern

Move Pointers

Advance both on match, advance i only for lowercase

Validate Result

Check if pattern pointer reached the end

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>

int isMatch(char* query, char* pattern) {
    int i = 0, j = 0;
    int qlen = strlen(query), plen = strlen(pattern);
    
    while (i < qlen) {
        if (j < plen && query[i] == pattern[j]) {
            i++;
            j++;
        } else if (islower(query[i])) {
            i++;
        } else {
            return 0;
        }
    }
    
    return j == plen;
}

int main() {
    char line[10000];
    fgets(line, sizeof(line), stdin);
    line[strcspn(line, "\n")] = 0;
    
    char* queries[1000];
    int count = 0;
    
    char* token = strtok(line + 1, ",");
    while (token) {
        while (*token == ' ' || *token == '"') token++;
        char* end = token + strlen(token) - 1;
        while (end > token && (*end == ' ' || *end == '"' || *end == ']')) *end-- = 0;
        
        queries[count] = malloc(strlen(token) + 1);
        strcpy(queries[count], token);
        count++;
        
        token = strtok(NULL, ",");
    }
    
    char pattern[1000];
    fgets(pattern, sizeof(pattern), stdin);
    pattern[strcspn(pattern, "\n")] = 0;
    
    printf("[");
    for (int i = 0; i < count; i++) {
        if (i > 0) printf(",");
        printf(isMatch(queries[i], pattern) ? "true" : "false");
    }
    printf("]\n");
    
    for (int i = 0; i < count; i++) {
        free(queries[i]);
    }
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n * m)

For each of n queries, scan through m characters once

✓ Linear Growth

Space Complexity

O(1)

Only using two pointer variables per query

✓ Linear Space

32.0K Views

Medium Frequency

~25 min Avg. Time

890 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Two Pointers Optimization — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler