Count Words with Given Prefix in DSA C - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of prefix count function

What is the output of the following C code that counts how many words start with the prefix "pre"?

DSA C

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

int countPrefix(char *words[], int n, char *prefix) {
    int count = 0;
    int prefixLen = strlen(prefix);
    for (int i = 0; i < n; i++) {
        if (strncmp(words[i], prefix, prefixLen) == 0) {
            count++;
        }
    }
    return count;
}

int main() {
    char *words[] = {"prefix", "preach", "prevent", "post", "prepare", "presentation"};
    int n = 6;
    int result = countPrefix(words, n, "pre");
    printf("%d\n", result);
    return 0;
}

A 5

B 3

C 4

D 6

💡 Hint

Count how many words start exactly with "pre".

The words starting with "pre" are: "prefix", "preach", "prevent", "prepare", and "presentation". That makes 5 words.

🧠 Conceptual

intermediate

Understanding prefix length in counting words

Why is it important to use the length of the prefix when comparing words to count how many start with that prefix?

A To compare the entire word length, which is always longer than the prefix

B To compare only the first characters equal to the prefix length, ensuring correct prefix matching

C To ignore the prefix length and compare the whole word for equality

D To count words that contain the prefix anywhere, not just at the start

💡 Hint

Think about how prefix matching works in strings.

Using the prefix length ensures only the start of each word is compared to the prefix, so words starting with the prefix are counted correctly.

🔧 Debug

advanced

Identify the bug in prefix counting code

What error will occur when running this code to count words starting with a prefix?

DSA C

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

int countPrefix(char *words[], int n, char *prefix) {
    int count = 0;
    for (int i = 0; i < n; i++) {
        if (strncmp(words[i], prefix, strlen(words[i])) == 0) {
            count++;
        }
    }
    return count;
}

int main() {
    char *words[] = {"apple", "app", "application"};
    int n = 3;
    int result = countPrefix(words, n, "app");
    printf("%d\n", result);
    return 0;
}

A The code will not compile due to missing header files

B The code will cause a segmentation fault due to invalid memory access

C The code compares more characters than the prefix length, causing incorrect counts

D The code correctly counts the words starting with the prefix

💡 Hint

Check the third argument of strncmp carefully.

The code uses strlen(words[i]) instead of strlen(prefix), so it compares too many characters, leading to wrong results.

❓ Predict Output

advanced

Output of prefix count with empty prefix

What is the output of this code when counting words starting with an empty prefix string?

DSA C

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

int countPrefix(char *words[], int n, char *prefix) {
    int count = 0;
    int prefixLen = strlen(prefix);
    for (int i = 0; i < n; i++) {
        if (strncmp(words[i], prefix, prefixLen) == 0) {
            count++;
        }
    }
    return count;
}

int main() {
    char *words[] = {"cat", "dog", "", "car"};
    int n = 4;
    int result = countPrefix(words, n, "");
    printf("%d\n", result);
    return 0;
}

A 4

B 3

C 0

D 1

💡 Hint

An empty prefix matches the start of every string.

Since the prefix is empty, every word starts with it, so all 4 words are counted.

🧠 Conceptual

expert

Why use strncmp instead of strcmp for prefix counting?

Why is strncmp preferred over strcmp when counting how many words start with a given prefix?

A strcmp ignores case, which is not suitable for prefix matching

B strcmp is faster and more efficient for prefix matching

C strncmp cannot compare strings, only characters

D strncmp compares only the first n characters, allowing prefix matching; strcmp compares entire strings

💡 Hint

Think about how prefix matching works with string comparison functions.

strncmp compares only the first n characters, which is exactly what is needed to check if a word starts with a prefix. strcmp compares full strings and would not work for prefixes.

Practice

1. What does the problem "Count Words with Given Prefix" ask you to do?

easy

A. Count how many words in a list start with a given prefix

B. Count the total number of characters in all words

C. Find the longest word in the list

D. Sort the words alphabetically

Solution

1. Step 1: Understand the problem statement

   The problem asks to find how many words start with a specific prefix string.

2. Step 2: Identify the key operation

   We need to check each word and count those that begin with the given prefix.

3. Final Answer:

   Count how many words in a list start with a given prefix -> Option A

4. Quick Check:

   Count words starting with prefix = Count how many words in a list start with a given prefix [OK]

Hint: Look for words starting exactly with the prefix [OK]

Common Mistakes:

• Counting total characters instead of words
• Looking for words containing prefix anywhere
• Sorting words instead of counting

2. Which of the following C code snippets correctly checks if a word starts with a given prefix prefix?

easy

A. strcmp(word, prefix) == 0

B. strncmp(word, prefix, strlen(prefix)) == 0

C. strstr(word, prefix) != NULL

D. strlen(word) == strlen(prefix)

Solution

1. Step 1: Understand string comparison functions

   strncmp compares first n characters; here n = length of prefix.

2. Step 2: Check which code confirms prefix match

   strncmp(word, prefix, strlen(prefix)) == 0 means word starts with prefix exactly.

3. Final Answer:

   strncmp(word, prefix, strlen(prefix)) == 0 -> Option B

4. Quick Check:

   strncmp with prefix length = 0 means prefix match [OK]

Hint: Use strncmp with prefix length to check start [OK]

Common Mistakes:

• Using strcmp which requires full string match
• Using strstr without checking start position
• Comparing lengths only

3. What is the output of the following C code?

char *words[] = {"apple", "app", "application", "banana"};
char prefix[] = "app";
int count = 0;
for (int i = 0; i < 4; i++) {
  if (strncmp(words[i], prefix, strlen(prefix)) == 0) {
    count++;
  }
}
printf("%d\n", count);

medium

A. 4

B. 2

C. 1

D. 3

Solution

1. Step 1: Check each word against prefix "app"

   "apple" starts with "app" (yes), "app" (yes), "application" (yes), "banana" (no).

2. Step 2: Count matching words

   Three words match the prefix, so count = 3.

3. Final Answer:

   3 -> Option D

4. Quick Check:

   Words starting with "app" = 3 [OK]

Hint: Count words where strncmp returns 0 for prefix length [OK]

Common Mistakes:

• Counting words that contain prefix anywhere
• Off-by-one errors in loop
• Incorrect prefix length in strncmp

4. Find the bug in this C code that counts words starting with prefix prefix:

int countWords(char *words[], int n, char *prefix) {
  int count = 0;
  for (int i = 0; i <= n; i++) {
    if (strncmp(words[i], prefix, strlen(prefix)) == 0) {
      count++;
    }
  }
  return count;
}

medium

A. Initialize count to 1 instead of 0

B. Use strcmp instead of strncmp

C. Loop condition should be i < n, not i <= n

D. strlen(prefix) should be replaced with strlen(words[i])

Solution

1. Step 1: Analyze loop boundary

   Loop runs from i = 0 to i <= n, which accesses words[n] (out of bounds).

2. Step 2: Correct loop condition

   Change to i < n to avoid accessing beyond array size.

3. Final Answer:

   Loop condition should be i < n, not i <= n -> Option C

4. Quick Check:

   Array index must be less than size [OK]

Hint: Use i < n for array loops to avoid overflow [OK]

Common Mistakes:

• Using <= instead of < in loops
• Confusing strcmp and strncmp usage
• Wrong length argument in strncmp

5. You have a list of words and want to count how many start with prefix pre. Which approach is best to optimize counting if you must do many prefix queries efficiently?

hard

A. Build a trie (prefix tree) from words and count nodes matching prefix

B. Use strncmp on each word for every query

C. Sort words and use binary search for prefix range

D. Store words in a hash set and check prefix membership

Solution

1. Step 1: Understand multiple prefix queries

   Checking each word with strncmp repeatedly is slow for many queries.

2. Step 2: Choose data structure for fast prefix counting

   Trie stores words by prefixes, allowing quick count of words with given prefix.

3. Step 3: Compare alternatives

   Binary search helps but trie is more direct for prefix counts; hash set doesn't support prefix queries well.

4. Final Answer:

   Build a trie (prefix tree) from words and count nodes matching prefix -> Option A

5. Quick Check:

   Trie = fast prefix count [OK]

Hint: Use trie for fast multiple prefix queries [OK]

Common Mistakes:

• Using linear search for many queries
• Ignoring trie benefits for prefix problems
• Using hash set which doesn't support prefix search