Longest Word in Dictionary through Deleting

Problem Statement

In this problem, you are provided with a string s and an array of strings named dictionary. The primary goal is to determine the longest string within the dictionary that can be reconstructed by deleting some characters in the string s. If multiple such strings exist that have the same maximum length, the one with the smallest lexicographical order should be chosen. If none of the strings in the dictionary can be formed by deleting some characters from s, the function should return an empty string.

Examples

Example 1

Input:

s = "abpcplea", dictionary = ["ale","apple","monkey","plea"]

Output:

"apple"

Example 2

Input:

s = "abpcplea", dictionary = ["a","b","c"]

Output:

"a"

Constraints

• 1 <= s.length <= 1000
• 1 <= dictionary.length <= 1000
• 1 <= dictionary[i].length <= 1000
• s and dictionary[i] consist of lowercase English letters.

Approach and Intuition

1. Understanding the Deletion Mechanism: To form a word from the dictionary by deleting some characters in s, each character in the chosen dictionary word must appear in s in the same order, though not necessarily consecutively.

2. Sequential Checking with Two Pointers:

   • First, sort the dictionary to manage the smallest lexicographical order by default when lengths are equal.
   • Use a two-pointer technique:
     • One pointer iterates over characters in s.
     • The second pointer tracks characters in the current dictionary word.
   • Move the pointer on s continuously and the pointer on the dictionary word only when there is a match.

3. Implementation Notes:

   • Process each word in the dictionary, using the two pointers to verify if the word can be formed by the sequence in s.
   • Track the longest word that can be successfully formed.
   • Return the longest word or an empty string if no words can be formed.

4. Optimization by Sorting:

   • Sorting the dictionary not only simplifies handling the lexicographical order but also efficiently checks through potential matches starting from longest to shortest.

Processing Examples:

• For s = "abpcplea", dictionary = ["ale","apple","monkey","plea"], while comparing apple and s, start checking from the first character of each string:
  • 'a' matches 'a', move both pointers.
  • 'p' matches 'p', move both pointers.
  • 'p' matches another 'p', continue.
  • 'l' matches 'l', and finally 'e' matches 'e', completing the word. Thus, "apple" can be formed and it's the longest.

Solutions

public class Solution {
    public boolean checkSubSequence(String a, String b) {
        int indexA = 0;
        for (int indexB = 0; indexB < b.length() && indexA < a.length(); indexB++)
            if (a.charAt(indexA) == b.charAt(indexB))
                indexA++;
        return indexA == a.length();
    }
    public String longestSubSequenceWord(String s, List<String> dictionary) {
        String maxLengthWord = "";
        for (String word : dictionary) {
            if (checkSubSequence(word, s)) {
                if (word.length() > maxLengthWord.length() || (word.length() == maxLengthWord.length() && word.compareTo(maxLengthWord) < 0))
                    maxLengthWord = word;
            }
        }
        return maxLengthWord;
    }
}