Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com

Problem

Submissions

Hints & solutions

Discuss

Complete String

Hard

0/120

Average time to solve is 40m

Contributed by

201 upvotes

Asked in companies

Problem statement

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.

Detailed explanation ( Input/output format, Notes, Images )

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

Sample Input 1 :

2
6
n ni nin ninj ninja ninga
2
ab bc

Sample Output 1 :

ninja
None

Explanation Of Sample Input 1 :

For test case 1 we have, 

All the prefixes of “ninja” -> “n”, “ni”, “nin”, “ninj” and “ninja” are present in array ‘A’. So, “ninja” is a valid answer whereas for “ninga” , the prefix “ning” is not present in array ‘A’.

So we output “ninja”.

For test case 2 we have, 

The prefixes of “ab” are “a” and “ab”. “a” is not present in array ‘A’. So, “ab” is not a valid answer.

The prefixes of “bc” are “b” and “bc”. “b” is not present in array ‘A’. So, “ab” is not a valid answer.

Since none of the strings is a valid answer we output “None”.

Sample Input 2 :

2
5
g a ak szhkb hy 
4
kez vfj vfjq vfjqo

Sample Output 2 :

ak
None

Hint 1

Hint 2

Try finding the prefix of each string and checking if they exist in the array.

Approaches (2)

Approach 1

Approach 2

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.

Time Complexity

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).

Space Complexity

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])).

(75% EXP penalty)

(100% EXP penalty)

Complete String

Akhil Rautela

Interview problems

Rolling Hash || Easy to Understand

#include <bits/stdc++.h> 
long long binpow(long long a, long long b, long long m) {
    a %= m;
    long long res = 1;
    while (b > 0) {
        if (b & 1)
            res = res * a % m;
        a = a * a % m;
        b >>= 1;
    }
    return res;
}
string completeString(int n, vector<string> &a){
    // Write your code here.
    sort(a.begin(), a.end(), [] (string &fir, string &sec) {
        if (fir.size() == sec.size()) {
            return fir < sec;
        }
        return fir.size() < sec.size();
        });
    long long mod = 1e9 + 7;
    long long poww = 31;
    int ans = -1;
    int curSize = 0;
    map <long long, int> pos;
    for (int i = 0; i < n; i++) {
        long long powNow = 1;
        long long hashHere = 0;
        for (char c : a[i]) {
            hashHere = (hashHere + (c - 'a' + 1) * powNow) % mod;
            powNow = (powNow * poww) % mod;
        }
        if (a[i].size() == 1) {
            pos[hashHere] = 1;
            if (a[i].size() > curSize) {
                ans = i;
                curSize = a[i].size();
            }
        }
        else {
            long long toSub = ((a[i][a[i].size() - 1] - 'a' + 1) * binpow(poww, a[i].size() - 1, mod)) % mod;
            long long hashLeft = (hashHere -  toSub + mod) % mod;
            if (pos.count(hashLeft)) {
                pos[hashHere] = a.size();
                if (a[i].size() > curSize) {
                    ans = i;
                    curSize = a[i].size();
                }
            }
        }
    }
    if (ans == -1) return "None";
    return a[ans];
}

beginners

programming

5 views

0 replies

0 upvotes

Sruti

Interview problems

Detailed Solution | Using Trie | C++

#include <bits/stdc++.h>
struct Node {
  Node *links[26];

  bool flag = false;

  bool containsKey(char ch) { return (links[ch - 'a'] != nullptr); }

  // To get child node
  Node *get(char ch) { return links[ch - 'a']; }

  // To set child node
  void put(char ch, Node *node) { links[ch - 'a'] = node; }

  // To mark node
  void setEnd() { flag = true; }

  /*To check if node
  marks the end of
  a word*/
  bool isEnd() { return flag; }
};
class Trie {
private:
  Node *root;

public:
  // Constructor
  Trie() {
    // Create a new root node for the Trie
    root = new Node();
  }

  // Method to insert a word into the Trie
  void insert(string word) {
    Node *node = root;
    // Iterate each character
    for (char ch : word) {
      /* If the character doesn't exist
      as a child node create a new node
      for the character*/
      if (!node->containsKey(ch)) {
        node->put(ch, new Node());
      }
      // Move to next node
      node = node->get(ch);
    }
    /*Mark last node
    as end of the word*/
    node->setEnd();
  }

  // To check if all prefixes of a given word exist in Trie
  bool checkIfAllPrefixExists(string word) {
    // Traversal from root node
    Node *node = root;
    // Iterate each character
    for (char ch : word) {
      // If character exists as child node
      if (node->containsKey(ch)) {
        // Move to next node
        node = node->get(ch);
        // Check if current node is end of word
        if (!node->isEnd())
          return false;
      } else {
        return false;
      }
    }
    // Return true if all prefixes exist
    return true;
  }
};

string completeString(int n, vector<string> &words) {
  // Create a Trie object
  Trie *obj = new Trie();
  // Insert each word into the Trie
  for (const auto &word : words)
    obj->insert(word);

  // Initialize variable
  string longest = "";
  // Iterate through each word in the vector
  for (const auto &word : words) {
    // Check if all prefixes of the word exist
    if (obj->checkIfAllPrefixExists(word)) {
      // Update the longest string if the current word
      // is longer or lexicographically smaller
      if (word.size() > longest.size() ||
          (word.size() == longest.size() && word < longest)) {
        // Update the longest string
        longest = word;
      }
    }
  }
  // Return an empty string
  if (longest.empty())
    return "None";
  // Return longest string
  return longest;
}

440 views

0 replies

1 upvote

Coderfriend

Interview problems

Doubt

If we use Trie then the TC = O(N * len) where both are 1e5 then the TC should be 1e10 which should give TLE. But it passes correctly. Why???

41 views

1 reply

4 upvotes

Mohit Garg

Interview problems

BETTER THAN 99% SOLUTIONS IN T.C. SIMPLE AND EASY TO UNDERSTAND CODE C++

#include <bits/stdc++.h>

class TrieNode{

public:

char data;

TrieNode* children[26];

bool isComplete;

TrieNode(char ch){

data = ch;

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

children[i]=NULL;

}

isComplete = false;

}

};

class Trie{

public:

TrieNode* root;

TrieNode* temp = root;

Trie(){

root = new TrieNode('\0');

root->isComplete = true;

}

bool insert(string word){

temp = root;

bool res = true;

for(int i=0; i<word.size(); i++){

int index=word[i]-'a';

if(temp->children[index]==NULL){

temp->children[index]=new TrieNode(word[i]);

}

res = res&temp->isComplete;

temp = temp->children[index];

}

temp->isComplete = res;

return temp->isComplete;

}

};

string completeString(int n, vector<string> &a){

// Write your code here.

sort(a.begin(), a.end());

Trie* t = new Trie();

string ans = "";

for(int i=0; i<a.size(); i++){

if(t->insert(a[i])){

if(a[i].size()>ans.size()){

ans = a[i];

}

return ans.size()>0 ? ans:"None";

}

453 views

0 replies

3 upvotes

DeadInside

Interview problems

Trie c++ solution

#include <bits/stdc++.h>

struct Node{

Node* Lists[256];

bool flag = false;

bool checkFlag()

{

return flag;

}

bool isPresent(char ch)

{

return (Lists[ch-0]!=NULL);

}

void createNewNode(char ch, Node* node)

{

Lists[ch-0]=node;

}

Node* nextNode(char ch)

{

return Lists[ch-0];

}

void setFlag()

{

flag=true;

}

};

class Trie{

public:

Node* root;

Trie()

{

root = new Node;

}

void insert(string word)

{

Node* node = root;

for(int i = 0; i<word.size(); i++)

{

if(!node->isPresent(word[i]))

{

node->createNewNode(word[i], new Node());

}

node = node->nextNode(word[i]);

}

node->setFlag();

}

void check(string word, string &largest)

{

Node* node = root;

bool got = true;

int i;

for(i = 0;i<word.size();i++)

{

node = node->nextNode(word[i]);

if(node->checkFlag())

continue;

else

{

got = false;

break;

}

if(i==word.size() && got==true)

{

if(word.size()>largest.size())

largest = word;

else if(word.size()==largest.size())

{

int comp = largest.compare(word);

if(comp>0)

largest = word;

}

};

string completeString(int n, vector<string> &a){

// Write your code here.

Trie trie;

string largest="";

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

{

trie.insert(a[i]);

}

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

{

trie.check(a[i], largest);

}

if(largest.size()!=0)

return largest;

return "None";

}

274 views

0 replies

1 upvote

Sundeep

Interview problems

using map

#include <bits/stdc++.h>

string completeString(int n, vector<string> &a){

// Write your code here.

map<string,int> mp;

for(string s:a){

mp[s];

}

int mapSize=mp.size();

unordered_map<string,int>::iterator it;

for(it=mp.begin() ; it!=mp.end(); it++ ){

string eachWord=it->first;

// cout<<eachWord<<"-";

for(int j=0;j<eachWord.size();j++){

string checkword=eachWord.substr(0,j+1);

if (mp.find(checkword) != mp.end()) {

it->second++;

}

int max_num=0;

string ans="None";

for (it = mp.begin(); it != mp.end(); it++) {

if (it->second > max_num && it->second==it->first.size()) {

max_num = max(max_num, it->second);

ans=it->first;

}

// cout<<max_num<<endl;

return ans;

}

224 views

0 replies

0 upvotes

Abhishek Yadav

Interview problems

Java Solution

class Node {
    Node[] links;
    boolean flag;

    Node() {
        links = new Node[26];
        flag = false;
    }

    boolean containsKey(char ch) {
        return (links[ch - 'a'] != null);
    }

    Node get(char ch) {
        return links[ch - 'a'];
    }

    void put(char ch, Node node) {
        links[ch - 'a'] = node;
    }

    void setEnd() {
        flag = true;
    }

    boolean isEnd() {
        return flag;
    }
}

class Trie {
    private Node root;

    Trie() {
        root = new Node();
    }

    void insert(String word) {
        Node node = root;
        for (int i = 0; i < word.length(); i++) {
            char ch = word.charAt(i);
            if (!node.containsKey(ch)) {
                node.put(ch, new Node());
            }
            node = node.get(ch);
        }
        node.setEnd();
    }

    boolean checkIfPrefixExist(String word) {
        Node node = root;
        for (int i = 0; i < word.length(); i++) {
            char ch = word.charAt(i);
            if (node.containsKey(ch)) {
                node = node.get(ch);
                if (!node.isEnd()) {
                    return false;
                }
            } else {
                return false;
            }
        }
        return true;
    }
}

public class Solution {

    public static String completeString(int n, String[] a) {
        Trie trie = new Trie();
        for (String it : a) {
            trie.insert(it);
        }
        String longest = "";
        for (String it : a) {
            if (trie.checkIfPrefixExist(it)) {
                if (it.length() > longest.length()) {
                    longest = it;
                } else if (it.length() == longest.length() && it.compareTo(longest) < 0) {
                    longest = it;
                }
            }
        }
        if (longest.equals("")) {
            return "None";
        }
        return longest;
    }
}

java

342 views

0 replies

1 upvote

SAMUAL HALDER

Interview problems

Strivers c++ solution :

#include <bits/stdc++.h>

class Node{

Node* links[26];

bool fl=false;

public:

bool contains(char ch){

return (links[ch-'a']!=NULL);

}

void put(char ch,Node* node){

links[ch-'a']=node;

}

Node* get(char ch){

return links[ch-'a'];

}

void setEnd(){

fl=true;

}

bool isEnd(){

return fl;

}

};

class Tries{

Node* root;

public:

Tries(){

root=new Node();

}

void insert(string word){

Node* node=root;

for(int i=0;i<word.size();i++){

if(!node->contains(word[i])){

node->put(word[i], new Node());

}

node=node->get(word[i]);

}

node->setEnd();

}

bool isPresant(string word){

Node* node=root;

for(int i=0;i<word.size();i++){

if(node->contains(word[i])){

node=node->get(word[i]);

if(node->isEnd()==false) return false;

}else{

return false;

}

return true;

}

};

string completeString(int n, vector<string> &a){

// Write your code here.

Tries trie;

for(auto &it:a){

trie.insert(it);

}

string len="";

for(auto &it:a){

if(trie.isPresant(it)){

if(it.size()>len.size()){

len=it;

}else if(it.size()==len.size() and it<len){

len=it;

}

if(len=="") return "None";

else return len;

}

763 views

0 replies

0 upvotes

Piyush mendhe

Interview problems

only 2 test cases are not passing , any idea on this

import java.util.* ;

import java.io.*;

class Solution {

public static class Node{

Node[] child;

boolean isEnd;

public Node()

{

child = new Node[26];

isEnd = false;

}

static Node root = new Node();

public static void insert(String str)

{

Node cur = root;

for(int i = 0 ; i<str.length();i++)

{

int idx = str.charAt(i) - 'a';

if(cur.child[idx]==null)

{

cur.child[idx]= new Node();

}

cur=cur.child[idx];

}

cur.isEnd = true;

}

public static boolean exist(String str)

{

Node cur = root;

boolean flag = true;

for(int i = 0 ; i<str.length();i++)

{

int idx = str.charAt(i) - 'a';

if(cur.child[idx]!=null)

{

cur=cur.child[idx];

flag = flag&cur.isEnd;

}

else{

return false;

}

return flag;

}

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

// Write your code here.

// Node obj = new Node();

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

{

insert(a[i]);

}

String longest ="";

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

{

if(exist(a[i]))

{

if(a[i].length()>longest.length())

{

longest = a[i];

}

else if(a[i].length()==longest.length())

{

longest = a[i];

}

if(longest =="")return "None";

return longest;

}

65 views

0 replies

0 upvotes

Akash Kalme

Interview problems

Brute Force using Map | C++

string completeString(int n, vector<string> &a){

// Write your code here.

map<string, int> mp;

for(auto i: a)

{

mp[i]++;

}

sort(a.begin(), a.end());

string res = "";

for(auto i: a)

{

string s = "";

bool flag = true;

for(int j=0; j<i.size(); j++)

{

s += i[j];

if(mp.find(s)==mp.end())

{

flag = false;

break;

}

if(flag && i.size()>res.size())

{

res = i;

}

if(res=="")

{

return "None";

}

return res;

}

155 views

1 reply

0 upvotes

Console