Complete String – Trie Based Solution

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.

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