Longest Word in Dictionary through Deleting (Find largest subsequence word from Dictionary)

Problem statement:

Longest Word in Dictionary through Deleting 

Find largest subsequence word from the given dictionary

Both the above problem statement is same.

Given a string and a string dictionary, find the longest string in the dictionary that can be formed by deleting some characters of the given string. If there are more than one possible results, return the longest word with the smallest lexicographical order. If there is no possible result, return the empty string.

Example 1:

Input:
s = "abpcplea", d = ["ale","apple","monkey","plea"]

Output: 
"apple"

Example 2:

Input:
s = "abpcplea", d = ["a","b","c"]

Output: 
"a"

Note:

1. All the strings in the input will only contain lower-case letters.
2. The size of the dictionary won't exceed 1,000.
3. The length of all the strings in the input won't exceed 1,000.

Solution

Before jumping to solve the problem, Give few mins gap and think. How can you approach for the problem...

Steps:

1. We need to have 2 for loops. One is to fetch word from dictionary and other for loop is iterate the word and check.

2. Write a logic to identify the largest subsequence of the word.

3. If we find more than 1 largest subsequence we need to return the smallest lexicographical order one.

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;

public class LongestWordSolution {
		
	public static void main(String[] args) {

		System.out.println(findLongestWord("bab", new String[] { "ba", "ab", "cad" }));
	}

	public static String findLongestWord(String s, String[] d) {
	
		if (s == null || d == null || s.isEmpty()) {
			return "";
		}

		String result = "";
		int max = 0;
		for (String str : d) {
			int count = 0;
			for (int i = 0, j = 0; i < str.length() && j < s.length();) {
				if (str.charAt(i) == s.charAt(j)) {
					i++;
					j++;
					count++;
				} else {
					j++;
				}
			}
			if (count == str.length()) {
				if (count == max) {
					if (result.compareTo(str) > 0) {
						result = str;
					}
				} else {
					max = Math.max(max, count);
					if (count == max) {
						result = str;
					}
				}
			}
		}

		return result;
	}
}

Time Complexity - O(MN) - M is the length of dictionary and N is the length of the string

Space Complexity - O(1)

Thanks for reading :) 

Whether this post is helpful?

Have something to add to this post? If you have any other quick thoughts/hints that you think people will find useful? Share it in the comments. feedback are welcome...