DSA

Complete String

Trie. Time O(nL), Space O(nL).

August 8, 2026

Practice Link

Ninja developed a love for arrays and strings so this time his teacher gave him an array of strings, ‘A’ of size ‘N’. Each element of this array is a string. The teacher taught Ninja about prefixes in the past, so he wants to test his knowledge. A string is called a complete string if every prefix of this string is also present in the array ‘A’. Ninja is challenged to find the longest complete string in the array ‘A’.If there are multiple strings with the same length, return the lexicographically smallest one and if no string exists, return "None". Note : String ‘P’ is lexicographically smaller than string ‘Q’, if :

There exists some index ‘i’ such that for all ‘j’ < ‘i’ , ‘P[j] = Q[j]’ and ‘P[i] < Q[i]’. E.g. “ninja” < “noder”.
If ‘P’ is a prefix of string ‘Q’, e.g. “code” < “coder”.

Approach#

Insert all strings into a Trie. A string is “complete” if every prefix of it also appears in the array — in Trie terms, every node along the string’s path must have isEnd = true. The checkPrefix function verifies this: traverse character by character and return false as soon as a node is missing or has isEnd = false. After building the Trie, iterate over all strings, check each one, and track the longest (lexicographically smallest on ties).

cpp


class TrieNode{
    public:
        bool isEnd;
        TrieNode* children[26];

        TrieNode(){
            isEnd = false;
            for(int i=0;i<26;i++)
                children[i] = NULL;
        }
};
class Trie{
    public:
        TrieNode* root;
        Trie()
        {
            root= new TrieNode();
        }

        void insert(string word)
        {
            TrieNode* curr = root;
            for(int i=0;i<word.length();i++)
            {
                int idx = word[i] -'a';
                if(curr->children[idx] == NULL)
                    curr->children[idx] = new TrieNode();
                curr = curr->children[idx];
            }
            curr->isEnd = true;
        }

        bool checkPrefix(string word)
        {
            TrieNode* curr = root;
            for(int i=0;i<word.length();i++)
            {
                int idx = word[i] -'a';
                if (curr->children[idx] != NULL) {
                    curr = curr->children[idx];
                    if (!curr->isEnd)
                      return false;
                }else
                    return false;
            }
            return true;
        }
};

string completeString(int n, vector<string> &a){
    Trie trie;
    for(auto i: a)
        trie.insert(i);

    string ans="";
    for(auto x: a)
    {
        if(trie.checkPrefix(x)){
            if(x.length() > ans.length())
                ans = x;
            else if(x.length() == ans.length() && x < ans)
                ans = x;
        }
    }

    if(ans.size()==0)
        return "None";
    return ans;
}

Time Complexity: O(nL)

Space Complexity: O(nL), where n is number of words, L is the maximum length of any word in a

DSACount Distinct SubstringsUsing Trie approach. Optimal — Time O(n^2), Space O(n^2).DSAGenerate ParenthesesGenerate all combinations of well-formed parentheses using backtracking. Optimal — Time O(4ⁿ/√n), Space O(n).6 min read DSAZigzag ConversionSimulate row-by-row traversal with direction flip. Optimal — Time O(n), Space O(n).

Approach#

Related articles