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

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of prefix count after insertions

What is the output of the following C++ code that inserts words into a prefix count structure and queries the count for prefix "app"?

DSA C++

class TrieNode {
public:
    int count = 0;
    TrieNode* children[26] = {nullptr};
};

class Trie {
public:
    TrieNode* root;
    Trie() { root = new TrieNode(); }
    void insert(const std::string& word) {
        TrieNode* node = root;
        for (char c : word) {
            int idx = c - 'a';
            if (!node->children[idx]) node->children[idx] = new TrieNode();
            node = node->children[idx];
            node->count++;
        }
    }
    int countPrefix(const std::string& prefix) {
        TrieNode* node = root;
        for (char c : prefix) {
            int idx = c - 'a';
            if (!node->children[idx]) return 0;
            node = node->children[idx];
        }
        return node->count;
    }
};

int main() {
    Trie trie;
    trie.insert("apple");
    trie.insert("app");
    trie.insert("application");
    trie.insert("apt");
    std::cout << trie.countPrefix("app") << std::endl;
    return 0;
}

A 4

B 3

C 2

D 1

💡 Hint

Count how many inserted words start with "app".

The words inserted are "apple", "app", "application", and "apt".

Only "apple", "app", and "application" start with "app".

So the count for prefix "app" is 3.

❓ Predict Output

intermediate

Count prefix with no matching words

What will be the output of the code when counting prefix "bat" after inserting words "cat", "car", "cart"?

DSA C++

class TrieNode {
public:
    int count = 0;
    TrieNode* children[26] = {nullptr};
};

class Trie {
public:
    TrieNode* root;
    Trie() { root = new TrieNode(); }
    void insert(const std::string& word) {
        TrieNode* node = root;
        for (char c : word) {
            int idx = c - 'a';
            if (!node->children[idx]) node->children[idx] = new TrieNode();
            node = node->children[idx];
            node->count++;
        }
    }
    int countPrefix(const std::string& prefix) {
        TrieNode* node = root;
        for (char c : prefix) {
            int idx = c - 'a';
            if (!node->children[idx]) return 0;
            node = node->children[idx];
        }
        return node->count;
    }
};

int main() {
    Trie trie;
    trie.insert("cat");
    trie.insert("car");
    trie.insert("cart");
    std::cout << trie.countPrefix("bat") << std::endl;
    return 0;
}

A 0

B 1

C 3

D 2

💡 Hint

Check if any inserted word starts with "bat".

None of the inserted words "cat", "car", "cart" start with "bat".

So the count for prefix "bat" is 0.

🔧 Debug

advanced

Identify the error in prefix count code

What error will the following code produce when counting prefix "app" after inserting "apple" and "app"?

DSA C++

class TrieNode {
public:
    int count = 0;
    TrieNode* children[26];
    TrieNode() {
        for (int i = 0; i < 26; i++) children[i] = nullptr;
    }
};

class Trie {
public:
    TrieNode* root;
    Trie() { root = new TrieNode(); }
    void insert(const std::string& word) {
        TrieNode* node = root;
        for (char c : word) {
            int idx = c - 'a';
            if (!node->children[idx]) node->children[idx] = new TrieNode();
            node = node->children[idx];
            node->count++;
        }
    }
    int countPrefix(const std::string& prefix) {
        TrieNode* node = root;
        for (char c : prefix) {
            int idx = c - 'a';
            if (!node->children[idx]) return 0;
            node = node->children[idx];
        }
        return node->count;
    }
};

int main() {
    Trie trie;
    trie.insert("apple");
    trie.insert("app");
    std::cout << trie.countPrefix("app") << std::endl;
    return 0;
}

A Compilation error: uninitialized array

B Runtime error: segmentation fault

C No error, output is 2

D Output is 0

💡 Hint

Check if children array is initialized properly.

The children array is initialized to nullptr in the constructor, so no segmentation fault occurs.

The count increments correctly for "apple" and "app".

Output is 2 because two words start with "app".

🧠 Conceptual

advanced

Understanding prefix count updates in Trie

If you insert the words "dog", "door", "dorm", and then delete "door" from a Trie that counts prefixes, what should happen to the prefix counts for "do"?

A The count for prefix "do" remains the same

B The count for prefix "do" becomes zero

C The count for prefix "do" decreases by 2

D The count for prefix "do" decreases by 1

💡 Hint

Deleting one word that starts with "do" affects counts accordingly.

Initially, three words start with "do": "dog", "door", "dorm".

Deleting "door" removes one word starting with "do".

So the count for prefix "do" decreases by 1.

🚀 Application

expert

Find number of words with prefix after multiple insertions

Given the following sequence of insertions into a prefix counting Trie: "test", "tester", "testing", "team", "teach", what is the count of words with prefix "te"?

A 5

B 3

C 2

D 4

💡 Hint

Count all words starting with "te".

The words are "test", "tester", "testing", "team", "teach".

All start with "te" including "team" and "teach".

So total 5 words start with "te".

But the question asks for count of words with prefix "te" which is 5.

Wait, options do not have 5 as correct answer except A.

Check carefully: all 5 start with "te".

So correct answer is 5 (option A).

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 specific prefix

B. Count the total number of words in a list

C. Find the longest word in a list

D. Replace the prefix in all words with another string

Solution

1. Step 1: Understand the problem statement

   The problem asks to find how many words start with a given prefix from a list of words.

2. Step 2: Identify the key operation

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

3. Final Answer:

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

4. Quick Check:

   Counting words with prefix = Count how many words in a list start with a specific prefix [OK]

Hint: Focus on words starting with prefix, not total words [OK]

Common Mistakes:

• Counting all words instead of only those with prefix
• Looking for longest word instead of counting
• Replacing prefix instead of counting

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

easy

A. if (word.compare(pref) == 1) { /* starts with prefix */ }

B. if (word == pref) { /* starts with prefix */ }

C. if (word.substr(1, pref.size()) == pref) { /* starts with prefix */ }

D. if (word.find(pref) == 0) { /* starts with prefix */ }

Solution

1. Step 1: Understand string::find usage

   Using word.find(pref) == 0 checks if pref is found at the start (index 0) of word.

2. Step 2: Check other options

   if (word == pref) { /* starts with prefix */ } checks equality, not prefix. if (word.substr(1, pref.size()) == pref) { /* starts with prefix */ } checks substring starting at index 1, which is wrong. if (word.compare(pref) == 1) { /* starts with prefix */ } compares strings but result 1 means greater, not prefix.

3. Final Answer:

   if (word.find(pref) == 0) { /* starts with prefix */ } -> Option D

4. Quick Check:

   find(pref) == 0 means prefix match [OK]

Hint: Use find(pref) == 0 to check prefix in C++ strings [OK]

Common Mistakes:

• Using equality instead of prefix check
• Checking substring from wrong index
• Misunderstanding compare() return values

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

std::vector words = {"apple", "app", "application", "banana"};
std::string prefix = "app";
int count = 0;
for (const auto& w : words) {
    if (w.find(prefix) == 0) {
        count++;
    }
}
std::cout << count << std::endl;

medium

A. 3

B. 2

C. 1

D. 4

Solution

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

   "apple" starts with "app" (count=1), "app" starts with "app" (count=2), "application" starts with "app" (count=3), "banana" does not.

2. Step 2: Count total matches

   Total words starting with "app" are 3.

3. Final Answer:

   3 -> Option A

4. Quick Check:

   Words starting with "app" = 3 [OK]

Hint: Count words where find(prefix) == 0 inside loop [OK]

Common Mistakes:

• Counting words that contain prefix anywhere
• Off-by-one errors in counting
• Ignoring words that exactly equal prefix

4. Identify the error in this C++ code snippet that tries to count words starting with prefix pref:

int count = 0;
for (auto w : words) {
    if (w.find(pref)) {
        count++;
    }
}

medium

A. The count variable should be initialized to -1

B. The loop variable should be a reference: auto& w

C. The condition should check if w.find(pref) == 0, not just w.find(pref)

D. The find function should be replaced with substr

Solution

1. Step 1: Understand find() return value

   find() returns position or npos. Using if(w.find(pref)) treats 0 as false, so words starting at index 0 are skipped.

2. Step 2: Correct condition for prefix check

   We must check if w.find(pref) == 0 to confirm prefix at start.

3. Final Answer:

   The condition should check if w.find(pref) == 0, not just w.find(pref) -> Option C

4. Quick Check:

   Check find() == 0 for prefix [OK]

Hint: Always compare find() result to 0 for prefix check [OK]

Common Mistakes:

• Using if(w.find(pref)) which fails for prefix at start
• Not using reference in loop (less critical here)
• Initializing count incorrectly

5. Given a list of words and a prefix, how would you efficiently count words starting with the prefix if the list is very large and queried multiple times?
Choose the best approach.

hard

A. Check each word with find(prefix) == 0 every time a query comes

B. Use a Trie (prefix tree) to store words and count prefix matches quickly

C. Sort the list and use binary search to find prefix range each time

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

Solution

1. Step 1: Understand repeated prefix queries

   Checking each word every time is slow for large lists and many queries.

2. Step 2: Use Trie data structure

   A Trie stores words by prefixes, allowing fast counting of words with given prefix in O(length of prefix) time.

3. Step 3: Evaluate other options

   Binary search after sorting helps but is less efficient for many queries. Hash set doesn't support prefix queries efficiently.

4. Final Answer:

   Use a Trie (prefix tree) to store words and count prefix matches quickly -> Option B

5. Quick Check:

   Trie = fast prefix counting [OK]

Hint: Use Trie for fast repeated prefix counts [OK]

Common Mistakes:

• Checking all words each query (slow)
• Using hash set which doesn't support prefix queries
• Ignoring Trie advantages for prefix problems