Largest word in dictionary by deleting some characters of given string
Last Updated :
24 Mar, 2025
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
Explanation: On removing characters at indexes 1,3,7 we can form string "apple" , similarly we can form strings "ale" and "plea" also, but "apple" is the longest string so we return "apple".
Input: dict = [ "pintu", "geeksfor", "geeksgeeks", " forgeek" ], str ="geeksforgeeks"
Output: geeksgeeks
Explanation: On removing characters at indexes 5,6,7 we can form string "geeksgeeks" , similarly we can form strings "geeksfor" and "forgeeks" also, but "geeksgeeks" is the longest string so we return "geeksgeeks" .
[Naive Approach] Using Sorting and Nested Loop – O(n^2logn) Time and O(1) Space
A naive 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 <bits/stdc++.h>
using namespace std;
bool isSubSequence(string d, string s){
int i = 0, j = 0;
while (i < d.size() && j < s.size()) {
if (d[i] == s[j]) {
i++;
}
j++;
}
return i == d.size();
}
string LongestWord(vector<string> d, string S) {
string res = "";
sort(d.begin(), d.end());
for (string word : d) {
// If the word is a subsequence and longer than
// current result
if (isSubSequence(word, S) && word.size() > res.size()) {
res = word;
}
}
return res;
}
int main(){
vector<string> dict = { "ale", "apple", "monkey", "plea" };
string str = "abpcplea";
cout << LongestWord(dict, str) << endl;
return 0;
}
#include <stdio.h>
#include <string.h>
int isSubSequence(char* str1, char* str2){
int m = strlen(str1);
int n = strlen(str2);
int j = 0;
for (int i = 0; i < n && j < m; i++)
if (str1[j] == str2[i])
j++;
return (j == m);
}
char* LongestWord(char** dict, int n, char* str){
char* result = "";
int length = 0;
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 result;
}
int main(){
char* dict[] = { "ale", "apple", "monkey", "plea" };
int n = sizeof(dict) / sizeof(dict[0]);
char str[] = "abpcplea";
printf("%s\n", LongestWord(dict, n, str));
return 0;
}
import java.util.*;
public class Main {
public static boolean isSubSequence(String d, String s) {
int i = 0, j = 0;
while (i < d.length() && j < s.length()) {
if (d.charAt(i) == s.charAt(j)) {
i++;
}
j++;
}
return i == d.length();
}
public static String LongestWord(List<String> d, String S) {
String res = "";
Collections.sort(d);
for (String word : d) {
// If the word is a subsequence and longer than current result
if (isSubSequence(word, S) && word.length() > res.length()) {
res = word;
}
}
return res;
}
public static void main(String[] args) {
List<String> dict = Arrays.asList("ale", "apple", "monkey", "plea");
String str = "abpcplea";
System.out.println(LongestWord(dict, str));
}
}
def isSubSequence(d, s):
i, j = 0, 0
while i < len(d) and j < len(s):
if d[i] == s[j]:
i += 1
j += 1
return i == len(d)
def LongestWord(d, s):
res = ""
d.sort()
for word in d:
# If the word is a subsequence
# and longer than current result
if isSubSequence(word, s) and len(word) > len(res):
res = word
return res
d = ["ale", "apple", "monkey", "plea"]
s = "abpcplea"
print(LongestWord(dict, str))
using System;
using System.Linq;
using System.Collections.Generic;
class Program {
public static bool IsSubSequence(string d, string s) {
int i = 0, j = 0;
while (i < d.Length && j < s.Length) {
if (d[i] == s[j]) {
i++;
}
j++;
}
return i == d.Length;
}
public static string LongestWord(List<string> d, string S) {
string res = "";
d.Sort();
foreach (string word in d) {
// If the word is a subsequence and longer than current result
if (IsSubSequence(word, S) && word.Length > res.Length) {
res = word;
}
}
return res;
}
static void Main() {
List<string> dict = new List<string> { "ale", "apple", "monkey", "plea" };
string str = "abpcplea";
Console.WriteLine(LongestWord(dict, str));
}
}
function isSubSequence(d, s) {
let i = 0, j = 0;
while (i < d.length && j < s.length) {
if (d[i] === s[j]) {
i++;
}
j++;
}
return i === d.length;
}
function LongestWord(d, s) {
let res = "";
d.sort();
for (let word of d) {
// If the word is a subsequence and longer
// than current result
if (isSubSequence(word, s) && word.length > res.length) {
res = word;
}
}
return res;
}
let d = ["ale", "apple", "monkey", "plea"];
let s = "abpcplea";
console.log(LongestWord(dict, str));
Time Complexity: O((n*k) +(n*(klogk))). Here n is the length of dictionary and k is the average word length in the dictionary. n*k for checking if a string is subsequence of str in the dict and nklogk for sorting each word in the dict.
[Expected Approach] Using Nested Loop – O(n^2) Time and O(1) Space
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.
C++
#include <bits/stdc++.h>
using namespace std;
bool isSubSequence(string s1, string s2){
int m = s1.size(), n = s2.size();
int j = 0;
for (int i = 0; i < n && j < m; i++)
if (s1[j] == s2[i])
j++;
return (j == m);
}
string LongestWord(vector<string> dict, string str){
string result = "";
int length = 0;
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 result;
}
int main()
{
vector<string> dict= { "pintu", "geeksfor", "geeksgeeks", "forgeek" };
string str = "geeksforgeeks";
cout << LongestWord(dict, str) << endl;
return 0;
}
#include <stdio.h>
#include <string.h>
int isSubSequence(char* s, char* s2) {
int m = strlen(str1), n = strlen(str2);
int j = 0;
for (int i = 0; i < n && j < m; i++) {
if (s1[j] == s2[i]) {
j++;
}
}
return (j == m);
}
char* LongestWord(char* dict[], int dictSize, char* str) {
char* result = "";
int length = 0;
for (int i = 0; i < dictSize; 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 result;
}
int main() {
char* dict[] = { "pintu", "geeksfor", "geeksgeeks", "forgeek" };
char str[] = "geeksforgeeks";
printf("%s\n", LongestWord(dict, 4, str));
return 0;
}
import java.util.*;
public class GFG {
public static boolean isSubSequence(String s1, String s2) {
int m = s1.length(), n = s2.length();
int j = 0;
for (int i = 0; i < n && j < m; i++) {
if (s1.charAt(j) == s2.charAt(i)) {
j++;
}
}
return j == m;
}
public static String LongestWord(List<String> dict, String str) {
String result = "";
int length = 0;
for (String word : dict) {
// Check if word is subsequence and longer than current result
if (length < word.length() && isSubSequence(word, str)) {
result = word;
length = word.length();
}
}
return result;
}
public static void main(String[] args) {
List<String> dict = Arrays.asList("pintu", "geeksfor", "geeksgeeks", "forgeek");
String str = "geeksforgeeks";
System.out.println(LongestWord(dict, str));
}
}
def isSubSequence(s1, s2):
m, n = len(s1), len(s2)
j = 0
for i in range(n):
if s1[j] == s2[i]:
j += 1
if j == m:
break
return j == m
def LongestWord(dict, str):
result = ""
length = 0
for word in dict:
# Check if word is subsequence and longer than current result
if length < len(word) and isSubSequence(word, str):
result = word
length = len(word)
return result
# Driver code
dict = ["pintu", "geeksfor", "geeksgeeks", "forgeek"]
str = "geeksforgeeks"
print(LongestWord(dict, str))
using System;
using System.Linq;
using System.Collections.Generic;
class Program {
public static bool IsSubSequence(string s1, string s2) {
int m = s1.Length, n = s2.Length;
int j = 0;
for (int i = 0; i < n && j < m; i++) {
if (s1[j] == s2[i]) {
j++;
}
}
return j == m;
}
public static string LongestWord(List<string> dict, string str) {
string result = "";
int length = 0;
foreach (string word in dict) {
// Check if word is subsequence and longer than current result
if (length < word.Length && IsSubSequence(word, str)) {
result = word;
length = word.Length;
}
}
return result;
}
static void Main() {
List<string> dict = new List<string> { "pintu", "geeksfor", "geeksgeeks", "forgeek" };
string str = "geeksforgeeks";
Console.WriteLine(LongestWord(dict, str));
}
}
function isSubSequence(s1, s2) {
let m = s1.length, n = s2.length;
let j = 0;
for (let i = 0; i < n; i++) {
if (s1[j] === s2[i]) {
j++; /
}
}
return j === m;
}
function LongestWord(dict, str) {
let result = "";
let length = 0;
for (let word of dict) {
// Check if word is subsequence and longer than current result
if (length < word.length && isSubSequence(word, str)) {
result = word;
length = word.length;
}
}
return result;
}
let dict = ["pintu", "geeksfor", "geeksgeeks", "forgeek"];
let str = "geeksforgeeks";
console.log(LongestWord(dict, str));
Time Complexity: O(n*k) Here n is the length of dictionary and k is the average word length in the dictionary.
Similar Reads
Computer Science Subjects