Complete String
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 : 1. There exists some index ‘i’ such that for all ‘j’

Question

Complete String

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 : 

1. There exists some index ‘i’ such that for all ‘j’ < ‘i’ , ‘P[j] = Q[j]’ and ‘P[i] < Q[i]’. E.g. “ninja” < “noder”.

2. If ‘P’ is a prefix of string ‘Q’, e.g. “code” < “coder”.

Example :

N = 4
A = [ “ab” , “abc” , “a” , “bp” ] 

Explanation : 

Only prefix of the string “a” is “a” which is present in array ‘A’. So, it is one of the possible strings.

Prefixes of the string “ab” are “a” and “ab” both of which are present in array ‘A’. So, it is one of the possible strings.

Prefixes of the string “bp” are “b” and “bp”. “b” is not present in array ‘A’. So, it cannot be a valid string.

Prefixes of the string “abc” are “a”,“ab” and “abc” all of which are present in array ‘A’. So, it is one of the possible strings.

We need to find the maximum length string, so “abc” is the required string.

Input Format :

The first line contains an integer 'T' which denotes the number of test cases to be run. Then the test cases follow.

The second line of each test case contains an integer ‘N’ denoting the size of array ‘A’.

The third line of each test case contains ‘N’ space-separated strings denoting the elements of array ‘A’.

Output format :

For each test case, print the longest string in ‘A’, such that every prefix of this string is also present 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" as answer.

Print the output of each test case in a new line.

Note :

You don’t need to print anything. It has already been taken care of. Just implement the given function.

Constraints :

1 <= T <= 10
1 <= N <= 10^5
1 <= A[i].length <= 10^5
A[i] only consists of lowercase english letters.
Sum of A[i].length <= 10^5 over all test cases

Time Limit : 1 sec

Accepted Answer

Brute Force

Approach :

We first find all the prefixes of each string in array ‘A’.
For each string ‘S’, we check if all the prefixes are part of the array ‘A’.
To check this, we mark the strings of array ‘A’ in a map.
If there are no such strings, we return “”.
We select the largest length string that has all prefixes in ‘A’.
We sort all the strings that satisfy the above criteria and return the lexicographically smallest one.

Algorithm :

Initialise a variable ‘ans’ as “”.
Initialise a hashmap ‘m’ with key type string and value type integer.
Traverse over all the strings ‘s’ of array ‘A’ and mark ‘m[s] = 1’.
Traverse over all the strings ‘s’ of array ‘A’ again :
Initialise a variable ‘flag’ as ‘1’.
If the size of current string is ‘sz’, run a loop from ‘i=0’ to ‘i=sz-1’ :
- Find the prefix ‘p’ of ‘s’ from index ‘j=0’ to ‘j=i’ and check if it is marked in the map ‘m’.
- If not, mark ‘flag’ as 0.
If the ‘flag’ = 1 :
- Check if current string ‘s’ is greater in size than ‘ans’ :
- If yes, update ‘ans’ to ‘s’.
- Else, if current string ‘s’ is same in length to ‘ans’ :
- Update ‘ans’ to the minimum of ‘ans’ and ‘s’.
If ‘ans’ is empty, then update “ans” to “None”.
Return ‘ans’ as the final result.

Space Complexity: OtherExplanation:

O(Sum(A[i])) where ‘Sum(A[i])’ is the sum of length of all words ‘A[i]’.

We are storing all strings in a map. Hence, the overall Space Complexity is O(Sum(A[i])).

Time Complexity: OtherExplanation:

O(Sum(A[i])*max(A[i])*log(N)), where ‘Sum(A[i])’ is the sum of length of all words ‘A[i]’, max(A[i]) is the maximum length of string in array ‘A’ and ‘N’ is the size of array ‘A’.

We are finding the prefixes of all strings ,searching them in a map, so the overall time complexity is O(Sum(A[i])*max(A[i])*N).

Python (3.5)

'''

    Time Complexity : O(Sum(A[i])*max(A[i])*log(N))

    Space Complexity : O(Sum(A[i]))



    where 'Sum(A[i])' is the sum of size of all words 'A[i]',

    'max(A[i])' is the maximum size of string in array 'A'.

    and 'N' is the size of array 'A'.

'''



from typing import *



def completeString(n: int, a: List[str])-> str:



    ans = ""



    mp = {}



    # Storing all strings in hashmap.

    for i in range(n):

        mp[a[i]] = 1

    



    for i in range(n):

        pre = ""

        flag = True



        # Traversing over all prefixes of the string 'a[i]'.

        for j in range(len(a[i])):



            pre += a[i][j]

            # If current prefix is not present in map, this string is invalid.

            if pre not in mp:

                flag = False

                break

            



        # Current string is a valid string.

        if flag:

            # If current string is longer than ans, we update it.

            if len(ans) < len(a[i]):

                ans = a[i]

            # If current string is of same size as 'ans', but lexicographically smaller, we update it.

            elif len(ans) == len(a[i]) and a[i] < ans:

                ans = a[i]

            

        

    



    # If there is no valid answer, we return "None".

    if len(ans) == 0:

      ans = "None"

    

    # Return the final result.

    return ans

Java (SE 1.8)

/*

    Time Complexity : O(Sum(A[i])*max(A[i])*log(N))

    Space Complexity : O(Sum(A[i]))



    where 'Sum(A[i])' is the sum of length of all words 'A[i]',

    'max(A[i])' is the maximum length of string in array 'A'.

    and 'N' is the size of array 'A'.

 */



import java.util.HashMap;



class Solution {



  public static String completeString(int n, String[] a) {



    String ans = "";



    HashMap < String, Integer > mp = new HashMap < > ();



    // Storing all strings in hashmap.

    for (int i = 0; i < n; i++) {

      mp.put(a[i], 1);

    }



    for (int i = 0; i < n; i++) {

      String pre = "";

      boolean flag = true;

      // Traversing over all prefixes of the string 'a[i]'.

      for (int j = 0; j < a[i].length(); j++) {

        pre += a[i].charAt(j);

        // If current prefix is not present in map, this string is invalid.

        if (mp.containsKey(pre));

        else {

          flag = false;

          break;

        }

      }



      // Current string is a valid string.

      if (flag) {

        // If current string is longer than ans, we update it.

        if (ans.length() < a[i].length()) {

          ans = a[i];

        }

        // If current string is of same length as 'ans', but lexicographically smaller, we update it.

        else if (ans.length() == a[i].length() && ans.compareTo(a[i]) > 0) {

          ans = a[i];

        }

      }

    }



    // If there is no valid answer, we return "None".

    if (ans.length() == 0) {

      ans = "None";

    }

    // Return the final result.

    return ans;

  }

}

C++ (g++ 5.4)

/*
    Time Complexity : O(Sum(A[i])*max(A[i])*log(N))
    Space Complexity : O(Sum(A[i]))

    where 'Sum(A[i])' is the sum of size of all words 'A[i]',
    'max(A[i])' is the maximum size of string in array 'A'.
    and 'N' is the size of array 'A'.
*/
#include

string completeString(int n, vector &a) {

    string ans = "";

    map mp;

    // Storing all strings in hashmap.
    for (int i = 0; i < n; i++) {
      mp[a[i]] = 1;
    }

    for (int i = 0; i < n; i++) {
      string pre = "";
      bool flag = true;
      // Traversing over all prefixes of the string 'a[i]'.
      for (int j = 0; j < a[i].size(); j++) {
        pre += a[i][j];
        // If current prefix is not present in map, this string is invalid.
        if (mp.count(pre));
        else {
          flag = false;
          break;
        }
      }

      // Current string is a valid string.
      if (flag) {
        // If current string is longer than ans, we update it.
        if (ans.size() < a[i].size()) {
          ans = a[i];
        }
        // If current string is of same size as 'ans', but lexicographically smaller, we update it.
        else if (ans.size() == a[i].size() && a[i] < ans) {
          ans = a[i];
        }
      }
    }

    // If there is no valid answer, we return "None".
    if (ans.size() == 0) {
      ans = "None";
    }
    // Return the final result.
    return ans;
}

Accepted Answer

Optimal Approach

Approach :

We will use Trie to solve this problem.
Trie will have two properties :
- Next pointer to link the next character of the string.
- Ending flag to denote if this is the last character of some string.
We will store each string in the trie.
Now we traverse the trie in dfs manner.
If while traversing , each level till now has the ending flag set on, then that means till this string, all prefixes of the string are present in the array ‘A’.
So, we check the maximum length strings that satisfy the above condition.
Example :
Let N = 4 and A[] = [“j”, “ji” , “jin” , jxn” ].
The trie structure will look like this :

We can notice that the ending at character ‘x’ is 0, as the word “jx” is not present in array ‘A’.
So, we traverse from ‘j’ to ‘ji’ to ‘jin’ and since the ending is 1, all are valid strings.
Since we want the longest among these, we select “jin”.
When we traverse from ‘j’ to ‘jx’ , we encounter ending 0 which tells that this and the further depth strings are not valid, so we don’t need to traverse to ‘jxn’.
So, “jin” is the desired answer.

Algorithm :

Initialise a class ‘Trie’ with ‘next’ and ‘ending’ as objects.
Traverse the array ‘A’ and insert each string in the trie.
Initialize a variable ‘ans’ as “”.
Now, traverse the trie in Depth First Search Manner.
- Initialize a variable ‘flag’ as ‘1’.
- If while traversing, any node has ‘ending flag’ as 0, then we return to avoid more depth searches.
- Else, all the prefixes till now are present in array ‘A’.
- If the string formed till now is larger than ‘ans’, update ‘ans’.
- If the string formed till now is of the same length as that of ‘ans’, update ‘ans’ as the minimum of the two. ( To return lexicographically smallest string )
If ‘ans’ is empty, then update “ans” to “None”.
Return ‘ans’ as the final result.

Space Complexity: OtherExplanation:

O(Sum(A[i])) where ‘Sum(A[i])’ is the sum of length of all words ‘A[i]’.

We are storing all strings in a Trie. Hence, the overall Space Complexity is O(Sum(A[i])).

Time Complexity: OtherExplanation:

O(Sum(A[i])), where ‘Sum(A[i])’ is the sum of length of all words ‘A[i]’.

We are storing each string in a Trie, so in the worst case, all the strings can be such that none of them are prefixes of the other string, so the overall time complexity is O(Sum(A[i])).

Python (3.5)

'''

    Time Complexity : O(Sum(A[i]))

    Space Complexity : O(Sum(A[i]))



    where 'Sum(A[i])' is the sum of length of all words 'A[i]'.



'''



from typing import *



class TrieNode:

    def __init__(self):

        self.children = [None for i in range(26)]

        self.isEnding = False



# Function to insert a string into trie.

def insert(word, root):



    node = root

    for c in word:

        i = ord(c) - ord('a')

        # If the next pointer is null for next character, allot the new memory.

        if node.children[i] == None:

            node.children[i] = TrieNode()

        

        node = node.children[i]

    

    # Mark the ending of word in trie.

    node.isEnding = True



# Function to check if this word has all prefixes in array.

def allPrefixed(word, root):

    node = root

    for c in word:

        i = ord(c) - ord('a')

        node = node.children[i]

        # Check if each prefix is a word in the trie.

        if node.isEnding == False:

            return False

        

    

    # We reach here if each prefix of word is present in array.

    return True



def completeString(n: int, a: List[str])-> str:



    # Initialise final answer as empty string.

    ans = ""



    root = TrieNode()



    # Insert each element of array into Trie.

    for i in a:

        insert(i, root)

    



    # Traverse over strings and check which of them have all prefixes present in array.

    for word in a:

        # This word is not valid.

        if allPrefixed(word, root) == False:

            continue

        

        # If current word is longer than 'ans'.

        if len(ans) < len(word):

            ans = word



        # If current word is of same length as 'ans', but is lexicographically smaller than 'ans'.

        elif len(ans) == len(word) and word < ans:

            ans = word

        

    



    # If no valid word is present, return "None".

    if len(ans)== 0:

        ans = "None"

    



    # Return the final result.

    return ans

C++ (g++ 5.4)

/*
    Time Complexity : O(Sum(A[i]))
    Space Complexity : O(Sum(A[i]))

    where 'Sum(A[i])' is the sum of size of all words 'A[i]'.
 */

// Trie data structure class.
struct trieNode 
{ 
    struct trieNode *child[26]; 
    bool isEnding;
}; 
struct trieNode *newTrieNode(void) 
{ 
    struct trieNode *newNode = new trieNode; 
    newNode->isEnding = false;
    for (int i = 0; i<26; i++) 
        newNode->child[i] = NULL; 
    return newNode; 
} 

// Functon to insert the word into the trie.
void insert(struct trieNode *root, string str) 
{ 
    int len = str.length(); 
    struct trieNode *pCrawl = root; 
  
    for (int level = 0; level    { 
        int index = str[level]-'a'; 
        if (!pCrawl->child[index]) 
            pCrawl->child[index] = newTrieNode(); 
        pCrawl = pCrawl->child[index]; 
    } 
    // Mark the ending of this word in trie.
    pCrawl ->isEnding = true;
}

  // Function to check if this word has all prefixes in array.
bool allPrefixed(struct trieNode *root, string word) {
    struct trieNode *pCrawl = root; 
    for (char c: word) {
      int i = c - 'a';
      pCrawl = pCrawl -> child[i];
      if(pCrawl == NULL || pCrawl->isEnding == false){
        return false;
      }
    }
    // We reach here if each prefix of word is present in array.
    return true;
}


string completeString(int n, vector &a) {

    // Initialise answer as empty string.
    string ans = "";

    struct trieNode *root = newTrieNode();

    // Insert each element of array into Trie.
    for (string word: a)
      insert(root, word);

    // Traverse over strings and check which of them have all prefixes present in array.
    for (string word: a) {
      if (!allPrefixed(root, word))
        continue;
      // If current word is longer than 'ans'.
      if (ans.size() < word.size()) {
        ans = word;
      }
      // If current word is of same size as 'ans', but is lexicographically smaller than 'ans'.
      else if (ans.size() == word.size() && word < ans) {
        ans = word;
      }
    }

    // If no valid word is present, return "None".
    if (ans.size() == 0) {
      ans = "None";
    }

    // Return the result.
    return ans;
  }

Java (SE 1.8)

/*

    Time Complexity : O(Sum(A[i]))

    Space Complexity : O(Sum(A[i]))



    where 'Sum(A[i])' is the sum of length of all words 'A[i]'.

 */



// Trie data structure class.

class TrieNode {

  public TrieNode[] children = new TrieNode[26];

  public boolean isEnding = false;

}



class Solution {



  private static TrieNode root = new TrieNode();



  public static String completeString(int n, String[] a) {



    // Initialise final answer as empty string.

    String ans = "";



    root=new TrieNode();



    // Insert each element of array into Trie.

    for (final String word: a) {

      insert(word);

    }



    // Traverse over strings and check which of them have all prefixes present in array.

    for (final String word: a) {

      // This word is not valid.

      if (!allPrefixed(word)) {

         continue;

      }

      // If current word is longer than 'ans'.

      if (ans.length() < word.length()) {

        ans = word;

      }

      // If current word is of same length as 'ans', but is lexicographically smaller than 'ans'.

      else if (ans.length() == word.length() && ans.compareTo(word) > 0) {

        ans = word;

      }

    }



    // If no valid word is present, return "None".

    if (ans.length() == 0) {

      ans = "None";

    }



    // Return the final result.

    return ans;

  }



  // Function to insert a string into trie.

  private static void insert(final String word) {

    TrieNode node = root;

    for (final char c: word.toCharArray()) {

      final int i = c - 'a';

      // If the next pointer is null for next character, allot the new memory.

      if (node.children[i] == null) {

        node.children[i] = new TrieNode();

      }

      node = node.children[i];

    }

    // Mark the ending of word in trie.

    node.isEnding = true;

  }



  // Function to check if this word has all prefixes in array.

  private static boolean allPrefixed(final String word) {

    TrieNode node = root;

    for (final char c: word.toCharArray()) {

      final int i = c - 'a';

      node = node.children[i];

      // Check if each prefix is a word in the trie.

      if (!node.isEnding) {

        return false;

      }

    }

    // We reach here if each prefix of word is present in array.

    return true;

  }

}

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.

Note :

Example :

Input Format :

Output format :

Note :

Constraints :

Top Nagarro Software Developer interview questions & answers

Popular interview questions of Software Developer

Top HR questions asked in Nagarro Software Developer