Longest Valid Word with All Prefixes
Given an array of N strings words[]. Find longest string in words[] such that such that every prefix of it is also in words[]. If there are multiple answers print the lexicographically shortest string.
Examples:
Input: words = {“a” , “banana” , “app” , “apply” , “ap” , “appl” , “apple”}
Output: apple
Explanation:
- For the first string “a”, only prefix is “a” and it is present in the words[] array, so this is a valid string.
- For the second string “banana”, prefixes are: “b”, “ba”, “ban”, “bana”, “banan” and “banana”, but no prefix other than “banana” is present in words[] array.
- For the third string “app”, prefixes are: “a”, “aa” and “aap” and all the prefixes are present in words[] array, so this is a valid string.
- For the fourth string “apply”, prefixes are: “a”, “ap”, “app”, “appl” and “apply” but prefix “apply” is not present in the words[] array.
- For the fifth string “ap”, prefixes are: “a” and “ap” and both the prefixes are present in words[], so this is a valid string.
- For the sixth string “appl”, prefixes are: “a”, “ap”, “app” and “appl” and all the prefixes are present in words[], so this is a valid string.
- For the seventh string “apple”, prefixes are: “a”, “ap”, “app”, “appl” and “apple” and all the prefixes are present in words[], so this is a valid string.
Among all the valid strings, “apply” and “apple” are longest string having all the prefixes in words. Furthermore, “apple” is lexicographically smaller so “apple” is the answer.
Input: words = {“p”, “pr”, “pro”,”probl”, “problem”, “pros”, “process”, “processor” }
Output: pros
Approach: To solve the problem, follow the below idea:
We can solve this problem using Trie Data Structure. Initially, we can store all the strings in the trie. Now, we can again iterate over each string and while traversing over a string character by character, we keep check that there is always a word which ends at this character. This can be done by maintaining an extra flag, say eow which is set to true while inserting all the words into the trie. So, now when we again iterate over all the strings, we check character by character that whether the eow is true for every character. If eow is true for every character, the string is considered valid. Out of all the valid strings, we return the lexicographically smallest one.
Step-by-Step algorithm:
- Store all the words in a trie as trie always stores unique prefixes of Strings.
- Run a loop on the children array of the root Node
- In each iteration if the current Node is valid(!=null) and its eow is true then it means that the string formed till now exists in the words array and can act as a valid prefix for a longer String further.
- If the condition in the step 3 met call the same function recursively and append the current character in the input string (taken empty at start)
- In each recursive call the function will return a valid string which will be the longest string till that character in the trie , compare it with the other String from the same recursive call.
- In the end return the Longest String.
Below is the implementation of the approach:
#include <iostream>
#include <string>
using namespace std;
class Node {
public:
Node* children[26];
bool eow;
Node() {
for (int i = 0; i < 26; i++) {
children[i] = nullptr;
}
eow = false;
}
};
void insert(Node* root, const string& s) {
Node* curr = root;
for (char c : s) {
int idx = c - 'a';
if (curr->children[idx] == nullptr) {
curr->children[idx] = new Node();
}
curr = curr->children[idx];
}
curr->eow = true;
}
string longestStringWithAllPrefix(Node* root, const string& pre) {
if (root == nullptr) {
return pre;
}
string longest = pre;
for (int i = 0; i < 26; i++) {
if (root->children[i] != nullptr && root->children[i]->eow) {
string s = pre + (char)(i + 'a');
string curr = longestStringWithAllPrefix(root->children[i], s);
if (curr.length() > longest.length()) {
longest = curr;
}
}
}
return longest;
}
int main() {
Node* root = new Node();
string words[] = {"apply", "apple", "a", "ap", "app", "appl", "banana"};
for (const string& s : words) {
insert(root, s);
}
cout << longestStringWithAllPrefix(root, "") << endl;
return 0;
}
/*package whatever //do not write package name here */
import java.io.*;
class GFG {
static class Node {
Node[] children = new Node[26];
boolean eow = false;
Node()
{
for (Node key : children) {
key = null;
}
}
}
public static void insert(Node root, String s)
{
Node curr = root;
for (int level = 0; level < s.length(); level++) {
int idx = s.charAt(level) - 'a';
if (curr.children[idx] == null) {
curr.children[idx] = new Node();
}
curr = curr.children[idx];
}
curr.eow = true;
}
public static String longestStringWithAllPrefix(Node root, String pre)
{
if (root == null) {
return pre;
}
String longest = pre;
for (int i = 0; i < 26; i++) {
if (root.children[i] != null && root.children[i].eow == true) {
String s = pre + (char)(i + 'a');
String curr = longestStringWithAllPrefix(root.children[i], s);
if (curr.length() > longest.length()) {
longest = curr;
}
}
}
return longest;
}
public static void main(String[] args)
{
Node root = new Node();
String words[] = { "apple", "a", "ap", "app","appl", "apply", "banana" };
for (String s : words) {
insert(root, s);
}
System.out.println(longestStringWithAllPrefix(root, ""));
}
}
class Node:
def __init__(self):
# Array to store child nodes for each letter of the alphabet
self.children = [None] * 26
# Flag to indicate the end of a word
self.eow = False
def insert(root, s):
# Function to insert a word into the trie
curr = root
for c in s:
# Calculate the index corresponding to the current character
idx = ord(c) - ord('a')
# If the child node for the current character does not exist, create one
if curr.children[idx] is None:
curr.children[idx] = Node()
# Move to the child node
curr = curr.children[idx]
# Mark the end of the word
curr.eow = True
def longest_string_with_all_prefix(root, pre):
# Function to find the longest string with a given prefix in the trie
if root is None:
return pre
# Initialize the longest string with the given prefix
longest = pre
for i in range(26):
# Iterate through the child nodes
if root.children[i] is not None and root.children[i].eow:
# If a valid word is found, recursively find the longest string with the updated prefix
s = pre + chr(i + ord('a'))
curr = longest_string_with_all_prefix(root.children[i], s)
# Update the longest string if the current one is longer
if len(curr) > len(longest):
longest = curr
return longest
if __name__ == "__main__":
# Create the root node of the trie
root = Node()
# List of words to insert into the trie
words = ["apply", "apple", "a", "ap", "app", "appl", "banana"]
# Insert each word into the trie
for word in words:
insert(root, word)
# Find and print the longest string with any given prefix in the trie
print(longest_string_with_all_prefix(root, ""))
# This code is contributed by rambabuguphka
using System;
class Node
{
public Node[] children = new Node[26]; // Array to store children nodes for each character
public bool eow; // Flag to mark if the node represents the end of a word
public Node()
{
for (int i = 0; i < 26; i++)
{
children[i] = null; // Initialize all children nodes to null
}
eow = false; // Initialize end of word flag to false
}
}
class Trie
{
// Function to insert a string into the trie
public static void Insert(Node root, string s)
{
Node curr = root;
foreach (char c in s)
{
int idx = c - 'a'; // Calculate index for character based on ASCII value
if (curr.children[idx] == null)
{
curr.children[idx] = new Node(); // Create new node if child does not exist
}
curr = curr.children[idx]; // Move to the next node
}
curr.eow = true; // Mark end of word
}
// Function to find the longest string with all prefixes
public static string LongestStringWithAllPrefix(Node root, string pre)
{
if (root == null)
{
return pre;
}
string longest = pre;
for (int i = 0; i < 26; i++)
{
if (root.children[i] != null && root.children[i].eow)
{
string s = pre + (char)(i + 'a'); // Append current character to prefix
string curr = LongestStringWithAllPrefix(root.children[i], s); // Recursively find longest string
if (curr.Length > longest.Length)
{
longest = curr; // Update longest string if necessary
}
}
}
return longest; // Return longest string with all prefixes
}
public static void Main(string[] args)
{
Node root = new Node(); // Create root node of trie
string[] words = { "apply", "apple", "a", "ap", "app", "appl", "banana" }; // Array of words to insert
foreach (string s in words)
{
Insert(root, s); // Insert each word into the trie
}
Console.WriteLine(LongestStringWithAllPrefix(root, "")); // Print longest string with all prefixes
}
}
class Node {
constructor() {
// Initialize an array to store children nodes (26 for each letter of the alphabet)
this.children = new Array(26).fill(null);
// Flag to indicate if the current node represents the end of a word
this.eow = false;
}
}
// Function to insert a word into the trie
function insert(root, s) {
let curr = root;
// Traverse through each character of the word
for (let level = 0; level < s.length; level++) {
// Calculate the index of the current character in the children array
let idx = s.charCodeAt(level) - 'a'.charCodeAt(0);
// If the child node does not exist, create a new one
if (curr.children[idx] === null) {
curr.children[idx] = new Node();
}
// Move to the child node
curr = curr.children[idx];
}
// Mark the end of the word
curr.eow = true;
}
// Function to find the longest string with all prefixes
function longestStringWithAllPrefix(root, pre) {
// If the root is null, return the prefix
if (root === null) {
return pre;
}
// Initialize the longest string with the given prefix
let longest = pre;
// Iterate through each child node
for (let i = 0; i < 26; i++) {
// If the child node exists and represents the end of a word
if (root.children[i] !== null && root.children[i].eow === true) {
// Construct the string with the current prefix and character
let s = pre + String.fromCharCode(i + 'a'.charCodeAt(0));
// Recursively find the longest string with all prefixes starting from this node
let curr = longestStringWithAllPrefix(root.children[i], s);
// Update the longest string if necessary
if (curr.length > longest.length) {
longest = curr;
}
}
}
return longest;
}
// Main function to test the trie
function main() {
// Create the root node of the trie
let root = new Node();
// Sample input words
let words = ["apple", "a", "ap", "app", "appl", "apply", "banana"];
// Insert each word into the trie
for (let s of words) {
insert(root, s);
}
// Find and print the longest string with all prefixes
console.log(longestStringWithAllPrefix(root, ""));
}
// Call the main function to start the program
main();
Output
apple
Time Complexity: O(N * M), where N is the size of array words[] and M is the maximum length of the string.
Auxiliary Space: O(26 * N * M)
Method 2
Approach: To solve the problem, follow the below idea:
We can solve this problem by sorting the words array in lexicographical order and then iterating over each word to check if all its prefixes are present in the array before it. If a word fails this condition, we can move to the next word in the sorted array. The first word that satisfies this condition will be the longest valid word.
Step-by-Step Algorithm:
- Sort the words array in lexicographical order.
- Iterate over each word in the sorted array.
- For each word, iterate over all its prefixes and check if they are present in the array before it.
- If all prefixes are present, return the current word as the longest valid word.
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
string longestValidWord(vector<string>& words) {
// Sort the words vector in lexicographical order
sort(words.begin(), words.end());
// Initialize the longest valid word as an empty string
string longestWord = "";
// Iterate over each word in the sorted vector
for (const string& word : words) {
bool valid = true;
// Iterate over all prefixes of the current word
for (int i = 1; i < word.length(); i++) {
string prefix = word.substr(0, i);
// Check if the prefix is not in the vector before the current word
if (!binary_search(words.begin(), words.end(), prefix)) {
valid = false;
break;
}
}
// If all prefixes are valid, update the longest valid word
if (valid && (word.length() > longestWord.length() || (word.length() == longestWord.length() && word < longestWord))) {
longestWord = word;
}
}
return longestWord;
}
int main() {
// Example usage
vector<string> words = {"apply", "apple", "a", "ap", "app", "appl", "banana"};
cout << longestValidWord(words) << endl; // Output: "apple"
return 0;
}
import java.util.Arrays;
public class Main {
public static String longestValidWord(String[] words) {
// Sort the words array in lexicographical order
Arrays.sort(words);
// Initialize the longest valid word as an empty string
String longestWord = "";
// Iterate over each word in the sorted array
for (String word : words) {
boolean valid = true;
// Iterate over all prefixes of the current word
for (int i = 1; i < word.length(); i++) {
String prefix = word.substring(0, i);
// Check if the prefix is not in the array before the current word
if (Arrays.binarySearch(words, 0, Arrays.binarySearch(words, word), prefix) < 0) {
valid = false;
break;
}
}
// If all prefixes are valid, update the longest valid word
if (valid && (word.length() > longestWord.length() || (word.length() == longestWord.length() && word.compareTo(longestWord) < 0))) {
longestWord = word;
}
}
return longestWord;
}
public static void main(String[] args) {
// Example usage
String[] words = {"apply", "apple", "a", "ap", "app", "appl", "banana"};
System.out.println(longestValidWord(words)); // Output: "apple"
}
}
def longest_valid_word(words):
# Sort the words array in lexicographical order
words.sort()
# Initialize the longest valid word as an empty string
longest_word = ""
# Iterate over each word in the sorted array
for word in words:
valid = True
# Iterate over all prefixes of the current word
for i in range(1, len(word)):
prefix = word[:i]
# Check if the prefix is not in the array before the current word
if prefix not in words[:words.index(word)]:
valid = False
break
# If all prefixes are valid, update the longest valid word
if valid and (len(word) > len(longest_word) or (len(word) == len(longest_word) and word < longest_word)):
longest_word = word
return longest_word
# Example usage
words = ["apply", "apple", "a", "ap", "app", "appl", "banana"]
print(longest_valid_word(words)) # Output: "apple"
function longestValidWord(words) {
// Sort the words array in lexicographical order
words.sort();
// Initialize the longest valid word as an empty string
let longestWord = "";
// Iterate over each word in the sorted array
for (const word of words) {
let valid = true;
// Iterate over all prefixes of the current word
for (let i = 1; i < word.length; i++) {
const prefix = word.substring(0, i);
// Check if the prefix is not in the array before the current word
if (!words.includes(prefix)) {
valid = false;
break;
}
}
// If all prefixes are valid, update the longest valid word
if (valid && (word.length > longestWord.length || (word.length === longestWord.length && word < longestWord))) {
longestWord = word;
}
}
return longestWord;
}
// Example usage
const words = ["apply", "apple", "a", "ap", "app", "appl", "banana"];
console.log(longestValidWord(words)); // Output: "apple"
Output
apple
Time Complexity: O(N^2 * M), where N is the number of words and M is the average length of words.
Auxiliary Space: O(N)