Taro Logo

Longest Word in Dictionary through Deleting

#1018 Most AskedMedium
20 views
Topics:
ArraysStringsTwo Pointers

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 possible result, return the 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.

Solution


Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

  1. What is the maximum length of the string `s` and the dictionary list?
  2. Can the dictionary contain duplicate words, and if so, how should they be handled if multiple words are valid?
  3. If multiple longest words can be formed by deleting characters from `s`, which one should I return (e.g., the lexicographically smallest one)?
  4. Can the input string `s` or any word in the dictionary be empty or null?
  5. Is the dictionary guaranteed to be sorted, or is it unsorted?

Brute Force Solution

Approach

The brute force strategy for this problem involves checking every single word in the dictionary to see if it can be formed by deleting characters from the given string. We compare each dictionary word to the main string. The goal is to find the longest possible word from the dictionary that can be created this way.

Here's how the algorithm would work step-by-step:

  1. Take the first word from the dictionary.
  2. See if you can make this dictionary word by removing some letters from the main string, one at a time. Imagine trying to spell out the dictionary word using the letters from the main string, but you're allowed to skip some letters in the main string.
  3. If you *can* make the dictionary word, remember its length. If this length is bigger than any previous dictionary word you were able to make, store this new dictionary word and its length.
  4. Take the next word from the dictionary and repeat the process of trying to form it from the main string by removing characters.
  5. Keep doing this for *every* word in the dictionary.
  6. At the end, return the longest dictionary word you found that you could make by deleting characters from the main string. If multiple words are the same length and are the longest, return the one that comes first alphabetically.

Code Implementation

def longest_word_in_dictionary_through_deleting(main_string, dictionary):
    longest_word_found = ""
    
    for dictionary_word in dictionary:
        dictionary_word_index = 0
        main_string_index = 0
        
        # Iterate to check if word can be formed by deleting
        while dictionary_word_index < len(dictionary_word) and main_string_index < len(main_string):
            if dictionary_word[dictionary_word_index] == main_string[main_string_index]:
                dictionary_word_index += 1
            main_string_index += 1
        
        # If dictionary word can be formed
        if dictionary_word_index == len(dictionary_word):
            # Find longest word
            if len(dictionary_word) > len(longest_word_found):
                longest_word_found = dictionary_word

            # Account for lexicographical order
            elif len(dictionary_word) == len(longest_word_found) and dictionary_word < longest_word_found:
                longest_word_found = dictionary_word
                
    return longest_word_found

Big(O) Analysis

Time Complexity
O(n*m*x) – Let n be the number of words in the dictionary, m be the average length of a word in the dictionary, and x be the length of the input string s. The algorithm iterates through each of the n words in the dictionary. For each word, it checks if it's a subsequence of s, which takes O(x) time in the worst case by linearly scanning s for each character of the dictionary word (length m). Therefore, the time complexity for checking all dictionary words is O(n*m*x). The lexicographical comparison inside the loop does not change the overall complexity.
Space Complexity
O(1) – The provided algorithm iterates through the dictionary but primarily uses variables to track the longest word found so far and its length. It compares words without creating significant auxiliary data structures that scale with the size of the dictionary or the main string. Therefore, the extra space required is constant, independent of the input size, and thus has a space complexity of O(1).

Optimal Solution

Approach

We need to find the longest word from a given dictionary that can be formed by deleting some characters from a given string. The key is to efficiently check if a dictionary word is a subsequence of the string, and keep track of the longest valid word found so far, prioritizing lexicographically smaller words when lengths are equal.

Here's how the algorithm would work step-by-step:

  1. Go through each word in the dictionary one by one.
  2. For each dictionary word, try to match its characters with the characters of the given string, making sure to maintain the order of the dictionary word's characters.
  3. If you can match all characters of the dictionary word by skipping some characters in the string, then the dictionary word can be formed by deleting characters from the string.
  4. Keep track of the longest dictionary word found so far that satisfies the condition above.
  5. If you find a dictionary word that's longer than the current longest word, update the longest word.
  6. If you find a dictionary word that's the same length as the current longest word, choose the one that comes earlier in alphabetical order.
  7. After checking all dictionary words, the word you've kept track of is the answer.

Code Implementation

def find_longest_word(source_string, dictionary):
    longest_word_found = ""

    for dictionary_word in dictionary:
        source_index = 0
        dictionary_index = 0

        # Iterate until either string is exhausted
        while source_index < len(source_string) and dictionary_index < len(dictionary_word):
            if source_string[source_index] == dictionary_word[dictionary_index]:
                dictionary_index += 1
            source_index += 1

        # Check if the dictionary word is a subsequence
        if dictionary_index == len(dictionary_word):
            # Check if the current word is longer.
            if len(dictionary_word) > len(longest_word_found):
                longest_word_found = dictionary_word
            
            # Pick lexicographically smaller word.
            elif len(dictionary_word) == len(longest_word_found) and dictionary_word < longest_word_found:
                longest_word_found = dictionary_word

    return longest_word_found

Big(O) Analysis

Time Complexity
O(n * m * x) – The algorithm iterates through each word in the dictionary, which we can denote as 'n' words. For each dictionary word, we check if it's a subsequence of the given string of length 'm'. The subsequence check involves iterating through both the dictionary word and the string, which in the worst case requires comparing each character of the dictionary word (length x) to the string. Therefore, the time complexity is O(n * m * x) where n is the number of words in the dictionary, m is the length of the input string, and x is the average length of the dictionary words.
Space Complexity
O(1) – The algorithm iterates through the dictionary but does not create any auxiliary data structures that scale with the size of the input string or the dictionary. It only stores a single variable to track the longest word found so far and a few temporary variables for comparison during each iteration. Therefore, the auxiliary space used remains constant, irrespective of the input size.

Edge Cases

Empty string s
How to Handle:
Return an empty string since no substring can be formed.
Empty dictionary d
How to Handle:
Return an empty string as no words can be formed through deletion.
Null s or d
How to Handle:
Throw an IllegalArgumentException or return null depending on requirements and language conventions.
Dictionary contains an empty string
How to Handle:
The empty string should be considered a valid result if no other word in dictionary is a valid subsequence.
s is very long, and the dictionary contains very long words
How to Handle:
Ensure the algorithm's time complexity is optimized to avoid Time Limit Exceeded errors, potentially prioritizing dictionary words by length.
Multiple dictionary words are valid subsequences and have the same length
How to Handle:
The solution should return the lexicographically smallest word among those having maximum length.
s contains Unicode characters
How to Handle:
Ensure the solution handles Unicode characters correctly using appropriate string manipulation methods of the language.
Dictionary contains duplicates
How to Handle:
The solution should correctly process the dictionary assuming potential duplicate words; removing them initially would be the best approach.
0/1916 completed