Prefix Search Algorithms and Implementation Strategies

Prefix search is a fundamental problem in computer science that involves efficiently finding all strings in a collection that start with a given prefix. This problem has wide applications in autocomplete systems, spell checkers, and search engines where fast string matching is crucial for user experience.

1. Pattern Restatement

Clarifying questions to ask the interviewer:

1. What is the expected input size and constraints? (e.g., number of queries, length of strings)
2. Are duplicate strings allowed in the input set?
3. What format should the output be returned in? (e.g., list of counts, boolean flags)
4. Can we modify the input array/structure during processing?
5. What is the target complexity for follow-up operations? (e.g., O(1) per query vs O(log n) per query)

Restatement of the pattern: The prefix search pattern involves efficiently finding how many strings in a dataset start with a given prefix. This is a classic trie-based problem where we build a data structure to support fast prefix lookups.

Signal words and constraint shape: Key indicators include "prefix", "startsWith", "search by prefix", or "count strings with given prefix". The constraint shape typically involves:

• Large dataset of strings (often 10³ to 10⁶ elements)
• Multiple prefix queries (often 10³ to 10⁵ queries)
• Need for sub-linear query performance (better than O(n) per query)

Assumptions made:

• Input strings consist of lowercase letters (a-z) for simplicity, though the solution can be extended to other character sets
• The problem is static (no insertions/deletions during query phase)
• We're optimizing for query efficiency over construction time

Scenario suitability: This pattern is best suited for static scenarios where we have a fixed set of strings and multiple prefix queries. It's less appropriate for streaming data or scenarios where we need to dynamically add/remove strings during query time.

The pattern fundamentally leverages the trie data structure's natural alignment with prefix matching, making it ideal for problems where we're repeatedly checking prefixes against a known collection of strings.

2. When to Use This Pattern

Signal words and constraint shapes in a problem statement that indicate this pattern:

• "Prefix" or "substring" matching requirements
• "Search for words that start with..."
• "Find all strings with common prefix"
• "Autocomplete" or "suggestion" functionality
• Input arrays of strings with shared prefixes
• Need for efficient prefix-based lookups

Why this pattern fits better than the most common alternatives: The prefix search pattern is ideal when we need to efficiently find all strings sharing a common prefix, particularly in scenarios like autocomplete systems or dictionary lookups. Unlike linear string matching (O(nm) where n is number of strings and m is average string length), prefix search leverages specialized data structures that can achieve O(m) lookup time after O(nm) preprocessing. This is superior to brute force approaches that would require checking each string individually.

Conditions where a variation or related pattern applies instead:

• When we only need to check if any string starts with a prefix, not enumerate all matches → Use simple trie or hash map lookup
• When we're dealing with dynamic insertion/deletion → Use dynamic data structures like balanced trees or hash maps
• When we're looking for exact matches rather than prefix matches → Use hash tables or simple string matching algorithms

The core insight that makes this pattern work: The fundamental insight is that we can organize strings in a way that allows us to traverse the trie structure efficiently by following the prefix path. When we reach a node in the trie that represents our search prefix, all strings in its subtree will share that prefix. This enables us to avoid re-computing string comparisons and instead leverage the tree structure for efficient prefix-based enumeration.

The pattern works best when we have a static or semi-static collection of strings where we can build an optimized data structure once and then perform multiple prefix queries efficiently.

3. Approach Evolution

Interview communication script:

My first instinct is to use a brute force approach where I check every string in the input array against the prefix, but that's O(n×m) where n is the number of strings and m is the average string length. That's inefficient because I'm doing redundant work - if I have strings like "apple", "application", "apply", and I'm searching for prefix "app", I don't want to check each string character-by-character from the start.

Let me think about how to optimize this. I notice that if I sort the strings first, then I can use binary search to find where strings with a given prefix start and end. But that's still O(n log n) for sorting plus O(log n) for search, which is better than brute force but not optimal.

I think there's a better approach using a Trie data structure. If I build a trie from all the strings, then I can traverse down the trie following the prefix characters. When I reach the end of the prefix, all strings in the subtree rooted at that node will have that prefix. This is O(m) where m is the length of the prefix, and building the trie is O(n×m).

The key insight is that I'm not just searching for one prefix - I'm building a structure that allows me to efficiently find all strings matching any prefix. This is particularly efficient when I have multiple prefix queries on the same dataset.

Brute-force approach and why it is not ideal:

The most straightforward approach is to iterate through every string in the input array and check if it starts with the given prefix. For each string, I would compare characters one by one until either the prefix is exhausted or a mismatch is found. This approach has O(n×m) time complexity where n is the number of strings and m is the average length of the strings.

This approach is inefficient because:

1. It performs redundant character comparisons for strings that don't match the prefix
2. It doesn't leverage any structure to speed up future queries
3. For multiple prefix searches, we're repeating the same work

Improved approach and the key optimization:

The improved approach uses a Trie (prefix tree) data structure. The key optimization is that once we build the trie, any prefix search becomes O(m) where m is the length of the prefix. This is because we only need to traverse the trie once following the prefix characters, and then collect all strings in the subtree.

The crucial insight is that we're not just searching - we're building a data structure that represents all prefixes in an efficient way. When we build the trie once, we can answer multiple prefix queries very quickly.

Final approach with step-by-step reasoning:

1. Build a Trie data structure where each node represents a character and contains references to child nodes
2. For each string in the input, insert it into the Trie character by character
3. When searching for a prefix, traverse the Trie following the prefix characters
4. Once we reach the end of the prefix in the Trie, collect all strings that are descendants of that node
5. Use a DFS traversal to gather all strings in the subtree rooted at the prefix end node

The invariant that must hold is that each node in the Trie represents a valid prefix of strings that pass through it, and leaf nodes represent complete strings.

Important invariants that must hold:

1. Each node in the Trie represents a valid prefix of strings in the dataset
2. The root-to-node path always forms a valid prefix of some string
3. Leaf nodes in the Trie represent complete strings from the input array
4. When traversing to find a prefix, we must reach a valid node or return empty set
5. The Trie structure maintains the hierarchical relationship between prefixes and strings

4. Data Structure Choice

For prefix search problems, the most appropriate data structure is a Trie (Prefix Tree).

Primary Data Structures Used

1. Trie Node Structure - The fundamental building block containing:

   • An array of child pointers (size 26 for lowercase English letters)
   • A boolean flag indicating end-of-word
   • Optional word storage for efficiency

2. Trie Root - The sentinel node that serves as the starting point for all prefix operations

Why Each Data Structure Is Needed

The Trie data structure is optimal for prefix search because:

• Efficient Prefix Lookup: Each character lookup takes O(1) time, making prefix operations O(m) where m is the prefix length
• Space Efficiency: Unlike hash tables, tries only store necessary characters, avoiding wasted space for unused prefixes
• Natural Extension: Easy to extend for autocomplete and word completion features

Time and Space Impact

Time Complexity:

• Insertion: O(m) where m is the word length
• Search: O(m) where m is the prefix length
• Space Usage: O(ALPHABET_SIZE × N × M) where N is number of words and M is average word length

Space Complexity: O(ALPHABET_SIZE × N × M) in worst case, but typically much better in practice due to shared prefixes

Helper Structures

• Character-to-index mapping: Simple array indexing (0-25) for efficient character access
• Word counter: Optional field to track how many words end at each node (useful for autocomplete counting)
• List of words: Optional storage at word-ending nodes to maintain actual words (useful for returning completions)

The Trie structure naturally supports the prefix search pattern by allowing efficient traversal of character-by-character matching while maintaining all necessary state information for completion and counting operations.

5. Algorithm Walkthrough

Let me trace through the algorithm with a concrete example to show how it works step-by-step.

Example: words = ["apple", "application", "apply", "app"], queries = ["app", "appl", "ap"]

Step 1: Build the Trie structure by inserting all words

• Insert "apple": Create nodes a-p-p-l-e, mark end of word
• Insert "application": Create nodes a-p-p-l-i-c-a-t-i-o-n, mark end of word
• Insert "apply": Create nodes a-p-p-l-y, mark end of word
• Insert "app": Create nodes a-p-p, mark end of word

Step 2: Process each query by traversing the Trie

• Query "app":

  • Start at root, move to 'a' → 'p' → 'p'
  • At node 'p', count = 3 (words ending here: "apple", "application", "apply")
  • Return 3

• Query "appl":

  • Start at root, move to 'a' → 'p' → 'p' → 'l'
  • At node 'l', count = 2 (words ending here: "apple", "application")
  • Return 2

• Query "ap":

  • Start at root, move to 'a' → 'p'
  • At node 'p', count = 4 (words ending here: "apple", "application", "apply", "app")
  • Return 4

Key Invariants Maintained:

• Each node's count field represents how many words pass through that node
• When we insert a word, we increment count on each node along the path
• When we search for prefix, we simply follow the path and return the count at the final node

Edge Case Handling:

• Empty query returns count at root (all words)
• Query not found in Trie returns 0
• Queries longer than any word return 0

The algorithm terminates correctly because every prefix query either:

1. Matches a complete path in the Trie (returns count at that node)
2. Fails to match at some point (returns 0)
3. Is longer than any existing word (returns 0)

6. Java Solution

import java.util.*;

public class PrefixSearch {
    
    // Trie node structure to store character mappings and end-of-word flag
    private static class TrieNode {
        Map<Character, TrieNode> children;
        boolean isEndOfWord;
        
        public TrieNode() {
            children = new HashMap<>();
            isEndOfWord = false;
        }
    }
    
    private TrieNode root;
    
    public PrefixSearch() {
        root = new TrieNode();
    }
    
    /**
     * Inserts a word into the trie
     * Time complexity: O(m) where m is the length of the word
     * Space complexity: O(m) in worst case for new nodes created
     */
    public void insert(String word) {
        TrieNode current = root;
        
        // Traverse each character of the word
        for (char c : word.toCharArray()) {
            // If current character doesn't exist, create new node
            current.children.putIfAbsent(c, new TrieNode());
            current = current.children.get(c);
        }
        
        // Mark end of word
        current.isEndOfWord = true;
    }
    
    /**
     * Checks if a word exists in the trie
     * Time complexity: O(m) where m is the length of the word
     */
    public boolean search(String word) {
        TrieNode current = root;
        
        // Traverse each character of the word
        for (char c : word.toCharArray()) {
            TrieNode node = current.children.get(c);
            if (node == null) {
                return false; // Word doesn't exist
            }
            current = node;
        }
        
        // Word exists only if it's marked as end of word
        return current.isEndOfWord;
    }
    
    /**
     * Checks if there's any word in the trie that starts with the given prefix
     * Time complexity: O(m) where m is the length of the prefix
     */
    public boolean startsWith(String prefix) {
        TrieNode current = root;
        
        // Traverse each character of the prefix
        for (char c : prefix.toCharArray()) {
            TrieNode node = current.children.get(c);
            if (node == null) {
                return false; // No word with this prefix exists
            }
            current = node;
        }
        
        // If we reach here, prefix exists in the trie
        return true;
    }
    
    /**
     * Returns all words that start with the given prefix
     * Time complexity: O(p + n*m) where p is prefix length, n is number of words with prefix, m is average word length
     */
    public List<String> getWordsWithPrefix(String prefix) {
        List<String> result = new ArrayList<>();
        TrieNode current = root;
        
        // Navigate to the end of prefix
        for (char c : prefix.toCharArray()) {
            TrieNode node = current.children.get(c);
            if (node == null) {
                return result; // No words with this prefix
            }
            current = node;
        }
        
        // Collect all words with this prefix using DFS
        dfs(current, prefix, result);
        return result;
    }
    
    /**
     * Helper method for depth-first search to collect all words
     */
    private void dfs(TrieNode node, String prefix, List<String> result) {
        if (node.isEndOfWord) {
            result.add(prefix);
        }
        
        // Visit all children in alphabetical order
        List<Character> sortedChars = new ArrayList<>(node.children.keySet());
        Collections.sort(sortedChars);
        
        for (char c : sortedChars) {
            dfs(node.children.get(c), prefix + c, result);
        }
    }
}

7. Complexity Analysis

Time Complexity: O(N × M) where N is the number of words and M is the average length of words.

The prefix search operation itself runs in O(M) time where M is the length of the search prefix. In the worst case, we need to check all words in our data structure, giving us O(N × M) total time complexity.

Space Complexity: O(ALPHABET_SIZE × N × M) where ALPHABET_SIZE is the size of the character set (typically 26 for lowercase English letters).

In the worst case, our Trie structure stores every character of every word. For a Trie with N words of average length M, we have at most N × M nodes, and each node can have up to ALPHABET_SIZE children. This results in O(ALPHABET_SIZE × N × M) space complexity.

Why these bounds are correct:

• Each word is processed once during insertion, and each character contributes to the Trie structure
• Search operations traverse at most M nodes in the Trie for a prefix of length M
• The space bound accounts for all possible paths in the Trie structure

Optimality: This solution is near-optimal for the prefix search problem. The O(N × M) time complexity is unavoidable since we must examine each word at least once to determine if it matches the prefix. The space complexity is also optimal for maintaining a complete Trie structure that supports all prefix queries efficiently.

The solution scales linearly with the number of words and their total character count, making it efficient for practical applications where the prefix length is typically small compared to the total dataset size.

8. Edge Cases & Pitfalls

Empty and Minimal Inputs

• Empty input: An empty array or list should return an empty result set, not null or throw exceptions
• Single element: A single string in the input array should work correctly with prefix queries
• Empty prefix: Searching for an empty prefix should return all strings in the collection

Duplicate Values and Repeated States

• Duplicate strings: Multiple occurrences of the same string should not affect prefix matching results
• Duplicate prefixes: Multiple strings sharing the same prefix should all be returned when querying that prefix

Boundary Conditions

• Prefix longer than string: Querying a prefix that exceeds the length of any string should return empty results
• Exact matches: When a query exactly matches a string, that string should be included in results
• Case sensitivity: The solution must handle case-sensitive prefix matching as specified (typically expected in FAANG problems)

Common Implementation Mistakes

• Not handling null inputs: Failing to check for null strings in the input array can cause NullPointerExceptions
• Incorrect prefix matching logic: Using substring comparison instead of proper prefix checking (e.g., str.startsWith(prefix) vs str.substring(0, prefix.length()).equals(prefix))
• Modifying input data: Mutating the original array or list during search operations violates the principle of immutability expected in FAANG systems
• Inefficient string operations: Using O(n) string concatenation or comparison instead of optimized prefix checking methods
• Missing edge case in sorting: When using sorted arrays, not accounting for strings that don't have the prefix at all

Memory and Performance Pitfalls

• Over-allocation: Pre-allocating result arrays that are too large for the actual number of matches
• Unnecessary object creation: Creating new string objects in loops instead of using substring operations or indices
• Inefficient search pattern: Using linear search for every query instead of pre-processing data structures like Tries or sorted arrays

9. Alternative Approaches

There are several alternative approaches to solving prefix search problems, each with different trade-offs:

Brute Force String Matching: For each query prefix, we could iterate through all strings and check if they start with the given prefix. This approach has O(m × n × p) time complexity where m is the number of queries, n is the number of strings, and p is the average prefix length. While simple to implement, it's inefficient for multiple queries on the same dataset.

Trie-Based Approach: Building a trie data structure where each node maintains a count of strings that pass through it. For prefix search, we traverse to the prefix node and return the count stored there. This is optimal for multiple queries with O(p) query time after O(∑|strings|) preprocessing. However, it requires additional space for the trie structure and is more complex to implement correctly.

Binary Search with Sorted Array: If we can sort the input strings, we can use binary search to find the first and last strings that start with a given prefix. This approach has O(n log n) preprocessing cost but O(log n + p) query time. It's particularly useful when queries are made on a static dataset and we can afford the initial sorting cost.

Suffix Array Approach: For advanced use cases with very large datasets, suffix arrays can be used to support prefix queries in O(log n + p) time. This is more complex but offers better space efficiency than tries for some applications.

The chosen solution using HashMap is preferred for its simplicity, good performance characteristics in most scenarios, and ease of implementation and maintenance.

10. Test Cases

public class PrefixSearchTestCases {
    public static void main(String[] args) {
        // Test case 1: Basic functionality
        String[] words1 = {"apple", "app", "application", "apply"};
        PrefixSearch ps1 = new PrefixSearch(words1);
        assert ps1.countWordsWithPrefix("app") == 4;
        assert ps1.countWordsWithPrefix("appl") == 3;
        assert ps1.countWordsWithPrefix("appz") == 0;

        // Test case 2: Empty prefix
        String[] words2 = {"hello", "world"};
        PrefixSearch ps2 = new PrefixSearch(words2);
        assert ps2.countWordsWithPrefix("") == 2;

        // Test case 3: No matches
        String[] words3 = {"cat", "dog", "bird"};
        PrefixSearch ps3 = new PrefixSearch(words3);
        assert ps3.countWordsWithPrefix("fish") == 0;

        // Test case 4: All words have same prefix
        String[] words4 = {"test", "testing", "testify"};
        PrefixSearch ps4 = new PrefixSearch(words4);
        assert ps4.countWordsWithPrefix("test") == 3;

        // Test case 5: Single character prefix
        String[] words5 = {"a", "aa", "aaa"};
        PrefixSearch ps5 = new PrefixSearch(words5);
        assert ps5.countWordsWithPrefix("a") == 3;
        assert ps5.countWordsWithPrefix("aa") == 2;
        assert ps5.countWordsWithPrefix("aaa") == 1;

        // Test case 6: Case sensitivity
        String[] words6 = {"Apple", "apple", "APPLE"};
        PrefixSearch ps6 = new PrefixSearch(words6);
        assert ps6.countWordsWithPrefix("app") == 1;
        assert ps6.countWordsWithPrefix("Apple") == 1;

        // Test case 7: Empty input array
        String[] words7 = {};
        PrefixSearch ps7 = new PrefixSearch(words7);
        assert ps7.countWordsWithPrefix("anything") == 0;

        // Test case 8: Single word
        String[] words8 = {"single"};
        PrefixSearch ps8 = new PrefixSearch(words8);
        assert ps8.countWordsWithPrefix("single") == 1;
        assert ps8.countWordsWithPrefix("sing") == 1;
        assert ps8.countWordsWithPrefix("singlex") == 0;

        System.out.println("All test cases passed!");
    }
}

11. Final Summary

The core idea is to efficiently support prefix-based string lookups by preprocessing all strings into a trie data structure, enabling O(m) search time where m is the prefix length. This solution works because tries naturally organize strings by their shared prefixes, making them ideal for autocomplete and dictionary-style problems. The implementation achieves optimal time complexity by avoiding redundant string comparisons and leveraging the trie's hierarchical structure to quickly prune irrelevant branches during search operations.