Find largest word in dictionary by deleting some characters of given string

Last Updated : 26 Apr, 2023

Giving a dictionary and a string ‘str’, find the longest string in dictionary which can be formed by deleting some characters of the given ‘str’.

Examples:

Input : dict = {"ale", "apple", "monkey", "plea"}   
        str = "abpcplea"  
Output : apple 

Input  : dict = {"pintu", "geeksfor", "geeksgeeks", 
                                        " forgeek"} 
         str = "geeksforgeeks"
Output : geeksgeeks

Asked In: Google Interview

This problem reduces to finding if a string is subsequence of another string or not. We traverse all dictionary words and for every word, we check if it is subsequence of given string and is largest of all such words. We finally return the longest word with given string as subsequence.

Below is the implementation of above idea

C

// C program to find largest word in Dictionary
// by deleting some characters of given string
 
#include <stdio.h>
#include <string.h>
 
// Returns 1 if str1[] is a subsequence of str2[].
// m is length of str1 and n is length of str2
int isSubSequence(char str1[], char str2[])
{
    int m = strlen(str1), n = strlen(str2);
 
    int j = 0; // For index of str1 (or subsequence)
 
    // Traverse str2 and str1, and compare current
    // character of str2 with first unmatched char
    // of str1, if matched then move ahead in str1
    for (int i = 0; i < n && j < m; i++)
        if (str1[j] == str2[i])
            j++;
 
    // If all characters of str1 were found in str2
    return (j == m);
}
 
// Returns the longest string in dictionary which is a
// subsequence of str.
char* findLongestString(char dict[][10], int size,
                        char str[])
{
    char* result = "";
    int length = 0;
 
    // Traverse through all words of dictionary
    for (int i = 0; i < size; i++) {
        char* word = dict[i];
        // If current word is subsequence of str and is
        // largest such word so far.
        if (length < strlen(word)
            && isSubSequence(word, str)) {
            result = word;
            length = strlen(word);
        }
    }
 
    // Return longest string
    return result;
}
 
// Driver program to test above function
int main()
{
    char dict[][10] = { "ale", "apple", "monkey", "plea" };
    char str[] = "abpcplea";
    char* longestString = findLongestString(
        dict, sizeof(dict) / sizeof(dict[0]), str);
    printf("%s\n", longestString);
    return 0;
}

C++

// C++ program to find largest word in Dictionary
// by deleting some characters of given string
#include <bits/stdc++.h>
using namespace std;
 
// Returns true if str1[] is a subsequence of str2[].
// m is length of str1 and n is length of str2
bool isSubSequence(string str1, string str2)
{
    int m = str1.length(), n = str2.length();
 
    int j = 0; // For index of str1 (or subsequence
 
    // Traverse str2 and str1, and compare current
    // character of str2 with first unmatched char
    // of str1, if matched then move ahead in str1
    for (int i = 0; i < n && j < m; i++)
        if (str1[j] == str2[i])
            j++;
 
    // If all characters of str1 were found in str2
    return (j == m);
}
 
// Returns the longest string in dictionary which is a
// subsequence of str.
string findLongestString(vector<string> dict, string str)
{
    string result = "";
    int length = 0;
 
    // Traverse through all words of dictionary
    for (string word : dict) {
        // If current word is subsequence of str and is
        // largest such word so far.
        if (length < word.length()
            && isSubSequence(word, str)) {
            result = word;
            length = word.length();
        }
    }
 
    // Return longest string
    return result;
}
 
// Driver program to test above function
int main()
{
    vector<string> dict
        = { "ale", "apple", "monkey", "plea" };
    string str = "abpcplea";
    cout << findLongestString(dict, str) << endl;
    return 0;
}

Java

// Java program to find largest
// word in Dictionary by deleting
// some characters of given String
 
import java.util.*;
 
class GFG
{
 
    // Returns true if str1[] is a 
    // subsequence of str2[]. m is 
    // length of str1 and n is length of str2 
    static boolean isSubSequence(String str1,
                                String str2) 
    {
        int m = str1.length(), n = str2.length();
 
        int j = 0; // For index of str1 (or subsequence) 
 
        // Traverse str2 and str1, and compare current 
        // character of str2 with first unmatched char 
        // of str1, if matched then move ahead in str1 
        for (int i = 0; i < n && j < m; i++)
        {
            if (str1.charAt(j) == str2.charAt(i)) 
            {
                j++;
            }
        }
 
        // If all characters of str1 
        // were found in str2 
        return (j == m);
    }
 
// Returns the longest String 
// in dictionary which is a 
// subsequence of str. 
    static String findLongestString(Vector<String> dict, 
                                            String str)
    {
        String result = "";
        int length = 0;
 
        // Traverse through all words of dictionary 
        for (String word : dict)
        {
             
            // If current word is subsequence of str 
            // and is largest such word so far. 
            if (length < word.length() &&
                isSubSequence(word, str))
            {
                result = word;
                length = word.length();
            }
        }
 
        // Return longest String 
        return result;
    }
 
    // Driver code
    public static void main(String[] args) 
    {
        String[] arr = {"ale", "apple", "monkey", "plea"};
        Vector dict = new Vector(Arrays.asList(arr));
        String str = "abpcplea";
        System.out.println(findLongestString(dict, str));
    }
} 
 
// This code is contributed by 29AjayKumar

Python3

# Python3 program to find largest word in Dictionary
# by deleting some characters of given string
 
# Returns true if str1[] is a subsequence of str2[].
# m is length of str1 and n is length of str2
def isSubSequence(str1, str2):
 
    m = len(str1);
    n = len(str2);
 
    j = 0; # For index of str1 (or subsequence
 
    # Traverse str2 and str1, and compare current
    # character of str2 with first unmatched char
    # of str1, if matched then move ahead in str1
    i = 0;
    while (i < n and j < m):
        if (str1[j] == str2[i]):
            j += 1;
        i += 1;
 
    # If all characters of str1 were found in str2
    return (j == m);
 
# Returns the longest string in dictionary which is a
# subsequence of str.
def findLongestString(dict1, str1):
    result = "";
    length = 0;
 
    # Traverse through all words of dictionary
    for word in dict1:
         
        # If current word is subsequence of str and is largest
        # such word so far.
        if (length < len(word) and isSubSequence(word, str1)):
            result = word;
            length = len(word);
 
    # Return longest string
    return result;
 
# Driver program to test above function
 
dict1 = ["ale", "apple", "monkey", "plea"];
str1 = "abpcplea" ;
print(findLongestString(dict1, str1));
     
# This code is conribued by mits

C#

// C# program to find largest
// word in Dictionary by deleting
// some characters of given String
using System;
using System.Collections.Generic;
 
class GFG
{
 
    // Returns true if str1[] is a 
    // subsequence of str2[]. m is 
    // length of str1 and n is length of str2 
    static bool isSubSequence(String str1,
                                String str2) 
    {
        int m = str1.Length, n = str2.Length;
 
        int j = 0; // For index of str1 (or subsequence) 
 
        // Traverse str2 and str1, and compare current 
        // character of str2 with first unmatched char 
        // of str1, if matched then move ahead in str1 
        for (int i = 0; i < n && j < m; i++)
        {
            if (str1[j] == str2[i]) 
            {
                j++;
            }
        }
 
        // If all characters of str1 
        // were found in str2 
        return (j == m);
    }
 
    // Returns the longest String 
    // in dictionary which is a 
    // subsequence of str. 
    static String findLongestString(List<String> dict, 
                                            String str)
    {
        String result = "";
        int length = 0;
 
        // Traverse through all words of dictionary 
        foreach (String word in dict)
        {
             
            // If current word is subsequence of str 
            // and is largest such word so far. 
            if (length < word.Length &&
                isSubSequence(word, str))
            {
                result = word;
                length = word.Length;
            }
        }
 
        // Return longest String 
        return result;
    }
 
    // Driver code
    public static void Main(String[] args) 
    {
        String[] arr = {"ale", "apple", "monkey", "plea"};
        List<String> dict = new List<String>(arr);
        String str = "abpcplea";
        Console.WriteLine(findLongestString(dict, str));
    }
} 
 
// This code contributed by Rajput-Ji

PHP

<?php
// PHP program to find largest word in Dictionary
// by deleting some characters of given string
 
// Returns true if str1[] is a subsequence of str2[].
// m is length of str1 and n is length of str2
function isSubSequence($str1, $str2)
{
    $m = strlen($str1);
    $n = strlen($str2);
 
    $j = 0; // For index of str1 (or subsequence
 
    // Traverse str2 and str1, and compare current
    // character of str2 with first unmatched char
    // of str1, if matched then move ahead in str1
    for ($i = 0; $i < $n && $j < $m; $i++)
        if ($str1[$j] == $str2[$i])
            $j++;
 
    // If all characters of str1 were found in str2
    return ($j == $m);
}
 
// Returns the longest string in dictionary which is a
// subsequence of str.
function findLongestString($dict, $str)
{
    $result = "";
    $length = 0;
 
    // Traverse through all words of dictionary
    foreach ($dict as $word)
    {
         
        // If current word is subsequence 
        // of str and is largest
        // such word so far.
        if ($length < strlen($word) && 
             isSubSequence($word, $str))
        {
            $result = $word;
            $length = strlen($word);
        }
    }
 
    // Return longest string
    return $result;
}
 
// Driver code
$dict = array("ale", "apple", "monkey", "plea");
$str = "abpcplea" ;
echo findLongestString($dict, $str);
     
// This code is conribued by mits
?>

Javascript

<script>
 
// JavaScript program to find largest word in Dictionary
// by deleting some characters of given string
 
// Returns true if str1[] is a subsequence of str2[].
// m is length of str1 and n is length of str2
function isSubSequence(str1, str2)
{
    var m = str1.length, n = str2.length;
 
    var j = 0; // For index of str1 (or subsequence
 
    // Traverse str2 and str1, and compare current
    // character of str2 with first unmatched char
    // of str1, if matched then move ahead in str1
    for (var i = 0; i < n && j < m; i++)
        if (str1[j] == str2[i])
            j++;
 
    // If all characters of str1 were found in str2
    return (j == m);
}
 
// Returns the longest string in dictionary which is a
// subsequence of str.
function findLongestString(dict, str)
{
    var result = "";
    var length = 0;
 
    // Traverse through all words of dictionary
 
    dict.forEach(word => {
        
        // If current word is subsequence of str and is
        // largest such word so far.
        if (length < word.length
            && isSubSequence(word, str)) {
            result = word;
            length = word.length;
        }
    });
 
    // Return longest string
    return result;
}
 
// Driver program to test above function
var dict
    = ["ale", "apple", "monkey", "plea"];
var str = "abpcplea";
document.write( findLongestString(dict, str));
 
 
</script>

Output

apple

Time Complexity: O(N*(K+n)) Here N is the length of dictionary and n is the length of given string ‘str’ and K – maximum length of words in the dictionary.
Auxiliary Space: O(1)

An efficient solution is we Sort the dictionary word. We traverse all dictionary words and for every word, we check if it is subsequence of given string and at last we check this subsequence is largest of all such subsequence.. We finally return the longest word with given string as subsequence.

C

#include <stdio.h>
#include <string.h>
 
// Returns true if str1[] is a subsequence of str2[].
// m is length of str1 and n is length of str2
int isSubSequence(char* str1, char* str2)
{
    int m = strlen(str1);
    int n = strlen(str2);
 
    int j = 0; // For index of str1 (or subsequence)
 
    // Traverse str2 and str1, and compare current
    // character of str2 with first unmatched char
    // of str1, if matched then move ahead in str1
    for (int i = 0; i < n && j < m; i++)
        if (str1[j] == str2[i])
            j++;
 
    // If all characters of str1 were found in str2
    return (j == m);
}
 
// Returns the longest string in dictionary which is a
// subsequence of str.
char* findLongestString(char** dict, int n, char* str)
{
    char* result = "";
    int length = 0;
 
    // Traverse through all words of dictionary
    for (int k = 0; k < n; k++) {
        char* word = dict[k];
 
        // If current word is subsequence of str and is
        // largest such word so far.
        if (length < strlen(word)
            && isSubSequence(word, str)) {
            result = word;
            length = strlen(word);
        }
    }
 
    // Return longest string
    return result;
}
 
// Driver program to test above function
int main()
{
    char* dict[] = { "ale", "apple", "monkey", "plea" };
    int n = sizeof(dict) / sizeof(dict[0]);
    char str[] = "abpcplea";
    printf("%s\n", findLongestString(dict, n, str));
    return 0;
}

C++

// C++ program to find largest word in Dictionary
// by deleting some characters of given string
#include <bits/stdc++.h>
using namespace std;
    string res="";
    void check(string d,string s)
    {
        int i=0;
        int j=0;
        while(i<d.size() && j<s.size())
        {
            if(d[i]==s[j])
            {
                i++;
                j++;
            }
            else
             j++;
        }
        if(i==d.size() && res.size()<d.size())
        {
            res=d;
        }
    }
   string LongestWord(vector<string> d,string S) {
     //sort the dictionary word
     // for smallest lexicographical order
      
     sort(d.begin(),d.end());
     for(string c:d)
     {
         check(c,S);
     }
     return res;
    }
// Driver program 
int main()
{
    vector<string> dict
        = { "ale", "apple", "monkey", "plea" };
    string str = "abpcplea";
    cout << LongestWord(dict, str) << endl;
    return 0;
}

Java

/*package whatever //do not write package name here */
import java.io.*;
import java.util.*;
 
class GFG {
    static String res="";
     
    static void check(String d,String s){
 
        int i = 0;
        int j = 0;
        while(i < d.length() && j < s.length()){
     
            if(d.charAt(i) == s.charAt(j)){
                i += 1;
                j += 1;
            }
            else
                j += 1;
     
            if(i == d.length() && res.length() < d.length()){
                res = d;
            }
        }
    }
     
    static String LongestWord(ArrayList<String>d,String S){
     
        // sort the dictionary word
        // for smallest lexicographical order
        Collections.sort(d);
     
        for(String c:d){
            check(c,S);
        }
         
        return res;
    }
     
// Drivers code
public static void main(String args[]){
         
    ArrayList<String>dict = new ArrayList<String>(Arrays.asList( "ale", "apple", "monkey", "plea"));
    String str = "abpcplea";
    System.out.println(LongestWord(dict, str));
}
}
 
// This code is contributed by shinjanpatra

Python3

# Python3 program to find largest word in Dictionary
# by deleting some characters of given string
 
res=""
 
def check(d,s):
    global res
    i = 0
    j = 0
    while(i < len(d) and j < len(s)):
 
        if(d[i] == s[j]):
            i += 1
            j += 1
        else:
            j += 1
 
        if(i == len(d) and len(res) < len(d)):
            res = d
 
def LongestWord(d, S):
   
    # sort the dictionary word
    # for smallest lexicographical order   
    d.sort()
 
    for c in d :
        check(c,S)
     
    return res
 
# Driver program 
dict = [ "ale", "apple", "monkey", "plea" ]
str = "abpcplea"
print(LongestWord(dict, str))
 
# This code is contributed by shinjanpatra

C#

// C# program for the above approach 
 
using System;
using System.Collections.Generic;
using System.Linq;
 
class GFG {
  static string res = "";
 
  static void check(string d, string s){
 
    int i = 0;
    int j = 0;
    while(i < d.Length && j < s.Length){
 
      if(d[i] == s[j]){
        i += 1;
        j += 1;
      }
      else
        j += 1;
 
      if(i == d.Length && res.Length < d.Length){
        res = d;
      }
    }
  }
 
  static string LongestWord(List<string> d, string S){
 
    // sort the dictionary word
    // for smallest lexicographical order
    d.Sort();
 
    foreach(string c in d){
      check(c, S);
    }
 
    return res;
  }
 
  // Drivers code
  public static void Main(string[] args){
 
    List<string> dict = new List<string>(new string[] { "ale", "apple", "monkey", "plea" });
    string str = "abpcplea";
    Console.WriteLine(LongestWord(dict, str));
  }
}
 
// This code is contributed by adityashatmfh

Javascript

<script>
 
// JavaScript program to find largest word in Dictionary
// by deleting some characters of given string
let res="";
function check(d, s)
{
    let i = 0;
    let j = 0;
    while(i < d.length && j < s.length)
    {
        if(d[i] == s[j])
        {
            i++;
            j++;
        }
        else
            j++;
        }
        if(i == d.length && res.length < d.length)
        {
            res = d;
        }
    }
function LongestWord(d,S)
{
 
    // sort the dictionary word
    // for smallest lexicographical order
    d.sort();
    for(let c of d)
    {
        check(c, S);
    }
    return res;
}
 
// Driver program 
let dict = [ "ale", "apple", "monkey", "plea" ];
let str = "abpcplea";
document.write(LongestWord(dict, str),"</br>");
 
// This code is contributed by shinjanpatra
 
</script>

Output

apple

Suggest improvement

Minimum number of subsequences required to convert one string to another

Largest divisible subset in array

Share your thoughts in the comments

Find largest word in dictionary by deleting some characters of given string

C

C++

Java

Python3

C#

PHP

Javascript

C

C++

Java

Python3

C#

Javascript

Please Login to comment...

Similar Reads

What kind of Experience do you want to share?