algoadvance

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

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.

Clarifying Questions

1. Should we consider only the exact characters and their sequence in the string s when forming the words from the dictionary?
   • Yes, the characters in the word formed must appear in the same order as they appear in s.
2. If there is a tie in the longest word length, should we return the one that comes first lexicographically?
   • Yes, return the smallest lexicographical order if there’s more than one result.

Strategy

1. Define a helper function is_subsequence(str1, str2) to check if str2 can be formed by deleting some characters from str1. This can be done using two pointers.
2. Sort the dictionary first by the length of the words in descending order. For words with the same length, sort them lexicographically in ascending order.
3. Iterate through the sorted dictionary and check if the current word is a subsequence of the given string s using the helper function.
4. Return the first word that satisfies the subsequence condition since the dictionary is sorted with priority rules mentioned.

Time Complexity

• Sorting the dictionary will take O(n log n) where n is the number of words in the dictionary.
• For each word in the dictionary, checking if it is a subsequence will take O(m) where m is the length of string s.
• Overall time complexity will be O(n log n + n * m), which should be efficient given the problem constraints.

Code

def findLongestWord(s, dictionary):
    def is_subsequence(x, y):
        it = iter(x)
        return all(c in it for c in y)
    
    # Sort the dictionary by length descending, lexically ascending
    dictionary.sort(key=lambda x: (-len(x), x))
    
    for word in dictionary:
        if is_subsequence(s, word):
            return word
    
    return ""

# Example usage:
s = "abpcplea"
dictionary = ["ale","apple","monkey","plea"]
print(findLongestWord(s, dictionary))  # Output: "apple"

This approach ensures we efficiently find the longest word that can be formed by deleting characters from s, considering both length and lexicographical order.

Try our interview co-pilot at AlgoAdvance.com

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?