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

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of prefix count after adding words

What is the output of the following Java code that counts words with a given prefix?

DSA Java

import java.util.*;

class PrefixCounter {
    private List<String> words = new ArrayList<>();

    public void addWord(String word) {
        words.add(word);
    }

    public int countWordsStartingWith(String prefix) {
        int count = 0;
        for (String w : words) {
            if (w.startsWith(prefix)) {
                count++;
            }
        }
        return count;
    }
}

public class Main {
    public static void main(String[] args) {
        PrefixCounter pc = new PrefixCounter();
        pc.addWord("apple");
        pc.addWord("app");
        pc.addWord("application");
        pc.addWord("banana");
        pc.addWord("apply");
        System.out.println(pc.countWordsStartingWith("app"));
    }
}

A 2

B 4

C 3

D 5

💡 Hint

Count all words that start exactly with "app".

The words starting with "app" are "apple", "app", "application", and "apply". So the count is 4.

🧠 Conceptual

intermediate

Understanding prefix counting complexity

If you have N words each of average length M, what is the time complexity of counting words starting with a prefix of length P using a simple list and startsWith check?

A O(N + P)

B O(P)

C O(N * M)

D O(N * P)

💡 Hint

Consider that startsWith compares characters up to prefix length P for each word.

For each of the N words, startsWith compares up to P characters, so total time is O(N * P).

🔧 Debug

advanced

Identify the error in prefix counting code

What error will this Java code produce when counting words with a prefix?

DSA Java

import java.util.*;

class PrefixCounter {
    private List<String> words = new ArrayList<>();

    public void addWord(String word) {
        words.add(word);
    }

    public int countWordsStartingWith(String prefix) {
        int count = 0;
        for (String w : words) {
            if (w.length() >= prefix.length() && w.substring(0, prefix.length()) == prefix) {
                count++;
            }
        }
        return count;
    }
}

public class Main {
    public static void main(String[] args) {
        PrefixCounter pc = new PrefixCounter();
        pc.addWord("apple");
        pc.addWord("app");
        System.out.println(pc.countWordsStartingWith("app"));
    }
}

A Prints 0 because string comparison uses '==' instead of equals()

B Throws StringIndexOutOfBoundsException if prefix is longer than word

C Compiles and prints 2 correctly

D Throws NullPointerException

💡 Hint

Java strings: use equals() for content comparison, == for references.

Prints 0 because string comparison uses '==' instead of equals().

🚀 Application

advanced

Choosing data structure for efficient prefix counting

Which data structure is best to efficiently count words starting with a given prefix among many words?

A Trie (Prefix Tree)

B HashSet of words

C ArrayList with linear search

D Stack

💡 Hint

Think about prefix-based search speed.

Trie stores words by prefixes allowing fast prefix counting in O(P) time, better than linear search.

❓ Predict Output

expert

Output of prefix count using Trie implementation

What is the output of this Java code that uses a Trie to count words with prefix "app"?

DSA Java

import java.util.*;

class TrieNode {
    Map<Character, TrieNode> children = new HashMap<>();
    int count = 0;
}

class Trie {
    private TrieNode root = new TrieNode();

    public void insert(String word) {
        TrieNode node = root;
        for (char c : word.toCharArray()) {
            node.children.putIfAbsent(c, new TrieNode());
            node = node.children.get(c);
            node.count++;
        }
    }

    public int countWordsStartingWith(String prefix) {
        TrieNode node = root;
        for (char c : prefix.toCharArray()) {
            if (!node.children.containsKey(c)) {
                return 0;
            }
            node = node.children.get(c);
        }
        return node.count;
    }
}

public class Main {
    public static void main(String[] args) {
        Trie trie = new Trie();
        trie.insert("apple");
        trie.insert("app");
        trie.insert("application");
        trie.insert("banana");
        trie.insert("apply");
        System.out.println(trie.countWordsStartingWith("app"));
    }
}

A 5

B 3

C 4

D 2

💡 Hint

Count increments at each node for inserted words with prefix.

Each inserted word increments count at nodes for its prefix. The prefix "app" node count is 4.

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. Find the longest word in a list

C. Count the total number of characters in all words

D. Sort the words alphabetically

Solution

1. Step 1: Understand the prefix concept

   The prefix is the starting part of a word. We need to check if words start with this prefix.

2. Step 2: Count matching words

   We count all words that begin with the given prefix from the list.

3. Final Answer:

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

4. Quick Check:

   Prefix means start of word = Count matching words [OK]

Hint: Focus on words starting exactly with the prefix [OK]

Common Mistakes:

• Counting words containing prefix anywhere, not just start
• Confusing prefix with suffix
• Counting characters instead of words

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

easy

A. word.endsWith(pref)

B. word.contains(pref)

C. word.equals(pref)

D. word.startsWith(pref)

Solution

1. Step 1: Recall Java String methods

   Java's startsWith method checks if a string begins with a given prefix.

2. Step 2: Match method to requirement

   Since we want to check the start, word.startsWith(pref) is correct.

3. Final Answer:

   word.startsWith(pref) -> Option D

4. Quick Check:

   startsWith checks prefix = word.startsWith(pref) [OK]

Hint: Use startsWith() to check prefix in Java strings [OK]

Common Mistakes:

• Using contains() which checks anywhere in string
• Using equals() which checks full string equality
• Using endsWith() which checks suffix

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

String[] words = {"apple", "app", "application", "banana"};
String prefix = "app";
int count = 0;
for (String w : words) {
    if (w.startsWith(prefix)) {
        count++;
    }
}
System.out.println(count);

medium

A. 3

B. 1

C. 2

D. 4

Solution

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

   Words starting with "app" are "apple", "app", and "application" (3 words).

2. Step 2: Count matching words

   Count increments 3 times for these words.

3. Final Answer:

   3 -> Option A

4. Quick Check:

   3 words start with "app" = 3 [OK]

Hint: Count words starting with prefix by checking each word [OK]

Common Mistakes:

• Counting only exact matches
• Counting words containing prefix anywhere
• Off-by-one errors in counting

4. The following code is intended to count words starting with a prefix but has a bug. What is the bug?

String[] words = {"cat", "car", "dog", "cart"};
String prefix = "car";
int count = 0;
for (int i = 0; i <= words.length; i++) {
    if (words[i].startsWith(prefix)) {
        count++;
    }
}
System.out.println(count);

medium

A. Prefix variable is not initialized

B. startsWith method is used incorrectly

C. Loop condition should be i < words.length, not i <= words.length

D. Array words is empty

Solution

1. Step 1: Analyze loop condition

   The loop runs from i = 0 to i <= words.length, which causes an IndexOutOfBoundsException because last index is words.length - 1.

2. Step 2: Correct loop condition

   Change condition to i < words.length to avoid accessing invalid index.

3. Final Answer:

   Loop condition should be i < words.length, not i <= words.length -> Option C

4. Quick Check:

   Array index max is length-1 = fix loop condition [OK]

Hint: Use i < array.length to avoid index errors [OK]

Common Mistakes:

• Using <= instead of < in loop condition
• Ignoring array index limits
• Misusing startsWith method

5. Given a list of words ["tree", "trie", "trigger", "trip", "trick"] and prefix "tri", which Java code snippet correctly counts the words starting with the prefix using streams?

hard

A. int count = Arrays.stream(words).map(w -> w.startsWith(prefix)).count();

B. long count = Arrays.stream(words).filter(w -> w.startsWith(prefix)).count();

C. long count = Arrays.stream(words).filter(w -> w.contains(prefix)).count();

D. int count = Arrays.stream(words).filter(w -> w.endsWith(prefix)).count();

Solution

1. Step 1: Use stream filter with startsWith

   The filter should keep words starting with the prefix using w.startsWith(prefix).

2. Step 2: Count filtered words

   Use count() to get the number of matching words. The result is a long type.

3. Final Answer:

   long count = Arrays.stream(words).filter(w -> w.startsWith(prefix)).count(); -> Option B

4. Quick Check:

   Filter with startsWith + count() = long count = Arrays.stream(words).filter(w -> w.startsWith(prefix)).count(); [OK]

Hint: Use stream filter with startsWith and count() for prefix count [OK]

Common Mistakes:

• Using map instead of filter
• Using contains instead of startsWith
• Using endsWith instead of startsWith