Count Prefixes of a Given String - Practice Coding Problems

Count Prefixes of a Given String - Problem

Array String Easy

You are given a string array words and a string s, where words[i] and s comprise only of lowercase English letters.

Return the number of strings in words that are a prefix of s.

A prefix of a string is a substring that occurs at the beginning of the string. A substring is a contiguous sequence of characters within a string.

Input & Output

Example 1 — Basic Case

$ Input: words = ["a", "b", "c", "ab", "bc", "abc"], s = "abc"

› Output: 3

💡 Note: The words "a", "ab", and "abc" are prefixes of "abc". "b", "c", and "bc" do not start at the beginning of "abc".

Example 2 — No Matches

$ Input: words = ["a", "a"], s = "aa"

› Output: 2

💡 Note: Both instances of "a" are prefixes of "aa". The string "a" matches the beginning of "aa".

Example 3 — Empty Prefix Not Allowed

$ Input: words = ["hello", "world", "hi"], s = "hi"

› Output: 1

💡 Note: Only "hi" exactly matches the target string "hi" as a prefix. "hello" and "world" don't match the beginning.

Constraints

1 ≤ words.length ≤ 1000
1 ≤ words[i].length, s.length ≤ 100
words[i] and s consist of lowercase English letters only

Visualization

Tap to expand

Understanding the Visualization

Input

Array of words and target string s

Check Prefixes

Test each word against beginning of s

Count Matches

Return number of valid prefixes found

Key Takeaway

🎯 Key Insight: A prefix must match the target string starting from the very beginning - any mismatch means it's not a valid prefix.

Asked in

a Amazon 15 M Microsoft 12

The key insight is to check if each word matches the beginning characters of the target string. The optimal approach uses built-in string prefix methods like startsWith() for clean, readable code. Time: O(n×m), Space: O(1).

Common Approaches

Approach	Time	Space	Notes
✓ Character-by-Character Comparison	O(n × m)	O(1)	Manually compare each character to check if word is a prefix of s
Built-in String Methods	O(n × m)	O(1)	Use language built-in startsWith() or similar functions for cleaner code

Character-by-Character Comparison — Algorithm Steps

Iterate through each word in the words array
For each word, compare characters one by one with string s from the beginning
If all characters match and word length ≤ s length, increment counter
Return the total count

Visualization

Tap to expand

Step-by-Step Walkthrough

Check Each Word

Iterate through words array

Compare Characters

Match each character with string s

Count Matches

Increment counter for valid prefixes

Code -

solution.c — C

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

int solution(char words[][101], int wordsSize, char* s) {
    int count = 0;
    int sLen = strlen(s);
    
    for (int i = 0; i < wordsSize; i++) {
        int wordLen = strlen(words[i]);
        if (wordLen <= sLen) {
            int isPrefix = 1;
            for (int j = 0; j < wordLen; j++) {
                if (words[i][j] != s[j]) {
                    isPrefix = 0;
                    break;
                }
            }
            if (isPrefix) {
                count++;
            }
        }
    }
    return count;
}

int main() {
    char line[10001], s[1001];
    fgets(line, sizeof(line), stdin);
    fgets(s, sizeof(s), stdin);
    s[strcspn(s, "\n")] = 0;
    
    char words[1000][101];
    int wordsSize = 0;
    
    char* token = strtok(line, "[,]\"");
    while (token != NULL && wordsSize < 1000) {
        if (strlen(token) > 0 && strcmp(token, "\n") != 0) {
            strcpy(words[wordsSize], token);
            wordsSize++;
        }
        token = strtok(NULL, "[,]\"");
    }
    
    int result = solution(words, wordsSize, s);
    printf("%d\n", result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n × m)

n words × average m characters per comparison

✓ Linear Growth

Space Complexity

O(1)

Only using counter variable, no extra data structures

✓ Linear Space

23.0K Views

Medium Frequency

~10 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

Character-by-Character Comparison — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler