Close Menu
    Code and Debug
    • Home
    • Our Courses
    • Blog
    • About Us
    • Contact Us
    Facebook X (Twitter) Instagram YouTube WhatsApp
    • Home
    • Our Courses
    • Blog
    • About Us
    • Contact Us
    Facebook Instagram YouTube LinkedIn WhatsApp
    Code and Debug – BlogCode and Debug – Blog
    Code and Debug – BlogCode and Debug – Blog
    Home»Data Structures & Algorithms»Complete String – Trie Based Solution
    Data Structures & Algorithms

    Complete String – Trie Based Solution

    codeanddebugBy codeanddebug1 September 2025No Comments4 Mins Read
    Share Facebook Twitter Pinterest LinkedIn Tumblr Reddit Telegram Email
    Featured image of a question to solve complete string
    Share
    Facebook Twitter LinkedIn Pinterest Email

    The Complete String problem asks us to find the longest string from a given list such that all its prefixes are also present in the list.

    • If multiple such strings exist, return the lexicographically smallest one.
    • If no such string exists, return "None".

    This problem is a classic application of the Trie data structure, which efficiently stores and checks prefixes.

    Here’s the [Problem Link] to begin with.


    Examples

    Example 1

    Input: ["n", "ni", "nin", "ninj", "ninja", "ninga"]
    Output: "ninja"
    Explanation: 
    All prefixes of "ninja" are present in the list:
    "n", "ni", "nin", "ninj", "ninja".

    Example 2

    Input: ["a", "ap", "app", "appl", "apple", "apply"]
    Output: "apple"
    Explanation: 
    Both "apple" and "apply" are valid, but "apple" is lexicographically smaller.

    Example 3

    Input: ["abc", "ab"]
    Output: "None"
    Explanation: 
    No string exists such that all its prefixes are present.

    Intuition and Approach

    To solve the Complete String problem, let’s carefully break it down:

    1. Store all words in a Trie:
      • Each character is inserted into the Trie.
      • Mark the end of each word.
    2. Check if a word is complete:
      • Traverse the word in the Trie.
      • For each character, verify if the current node is marked as the end of a word.
      • If any prefix is missing, the word is not complete.
    3. Find the best word:
      • Among all words that are complete strings, select the longest one.
      • If there are multiple with the same length, return the lexicographically smallest.

    This approach ensures correctness and efficiency by leveraging the prefix-checking power of the Trie.


    Code Implementation

    from sys import *
    from collections import *
    from math import *
    from typing import *
    
    class TrieNode:
        def __init__(self):
            self.children = {}
            self.is_end = False
    
    class Trie:
        def __init__(self):
            self.root = TrieNode()
    
        def insert(self, word: str) -> None:
            node = self.root
            for ch in word:
                if ch not in node.children:
                    node.children[ch] = TrieNode()
                node = node.children[ch]
            node.is_end = True
    
        def check_all_prefix(self, word: str) -> bool:
            node = self.root
            for ch in word:
                if ch not in node.children:
                    return False
                node = node.children[ch]
                if not node.is_end:  # prefix missing
                    return False
            return True
    
    def completeString(n: int, a: List[str]) -> str:
        trie = Trie()
        for word in a:
            trie.insert(word)
    
        best_word = "" 
        for word in a:
            if trie.check_all_prefix(word):
                if len(word) > len(best_word) or (len(word) == len(best_word) and word < best_word):
                    best_word = word
    
        return best_word if best_word != "" else "None"

    Code Explanation

    • TrieNode: Stores children (next characters) and a flag is_end to mark word endings.
    • insert(word): Adds a word character by character into the Trie.
    • check_all_prefix(word): Checks if every prefix of the given word exists in the Trie.
    • completeString:
      • Inserts all words into the Trie.
      • Iterates through each word, checking completeness.
      • Keeps track of the longest valid word, or lexicographically smallest if lengths tie.

    Dry Run

    Input: ["n", "ni", "nin", "ninj", "ninja", "ninga"]

    1. Insert all words into Trie.
    2. Check "ninja":
      • Prefixes "n", "ni", "nin", "ninj" all exist. ✅
    3. Check "ninga":
      • Prefix "ning" does not exist. ❌
    4. Final answer = "ninja".

    Output: "ninja"


    Time and Space Complexity

    • Insert: O(L) per word, where L = length of the word.
    • check_all_prefix: O(L) per word.
    • Total Complexity: O(N * L), where N = number of words, L = max word length.
    • Space Complexity: O(N * L), since the Trie stores all characters of all words.

    Conclusion

    The Complete String problem can be solved efficiently using a Trie by:

    1. Inserting all words.
    2. Checking if all prefixes of each word exist.
    3. Returning the longest valid word or "None".

    This approach ensures both accuracy and efficiency, making it a strong solution for coding interviews and competitive programming.


    Join our Advance DSA COURSE

    For any changes to the article, kindly email at code@codeanddebug.in or contact us at +91-9712928220.

    Medium Tries
    Share. Facebook Twitter Pinterest LinkedIn Tumblr Email
    Previous ArticleImplement Trie ll | Full Trie with Insert, Count, and Erase
    Next Article Count Distinct Substrings – Brute Force and Trie Approaches
    codeanddebug
    • Website

    Related Posts

    Data Structures & Algorithms

    Count Distinct Substrings – Brute Force and Trie Approaches

    1 September 2025
    Data Structures & Algorithms

    Implement Trie ll | Full Trie with Insert, Count, and Erase

    1 September 2025
    Data Structures & Algorithms

    Implement Trie (Prefix Tree) | Leetcode 208 | Efficient String Data Structure

    1 September 2025
    Add A Comment
    Leave A Reply Cancel Reply

    Categories
    • Data Structures & Algorithms (235)
      • Beginner (81)
      • Expert (51)
      • Intermediate (103)
    • Uncategorised (1)
    Recent Posts

    Count Distinct Substrings – Brute Force and Trie Approaches

    1 September 2025

    Complete String – Trie Based Solution

    1 September 2025

    Implement Trie ll | Full Trie with Insert, Count, and Erase

    1 September 2025

    Implement Trie (Prefix Tree) | Leetcode 208 | Efficient String Data Structure

    1 September 2025

    Roman to Integer | Leetcode 13 | Mapping and Subtraction Rule Solution

    1 September 2025
    Facebook Instagram YouTube LinkedIn WhatsApp
    © 2025 Code and Debug. All rights reserved.

    Type above and press Enter to search. Press Esc to cancel.