524. Longest Word in Dictionary through Deleting

MediumArrayTwo PointersStringSorting
Leetcode Link

Problem Description

The task is to find the longest string from a given list of words (the dictionary) that can be created by removing some of the characters from a given string s. If you can make multiple words of the same maximum length, you should return the one that comes first alphabetically. Should there be no words from the dictionary that can be formed, the answer would be an empty string.

To solve this problem, we need to determine if a given word in the dictionary can be formed by deleting characters from the string s. We use a two-pointer approach to compare characters of a dictionary word and the string s without rearranging any character's order.

Intuition

The intuition behind the solution is to use a two-pointer approach that can efficiently validate whether a word from the dictionary is a subsequence of the string s. Here's how we proceed:

  • Initialize two pointers, i for the index in the string s and j for the index in the current dictionary word.
  • Increment i each time we examine a character in s.
  • Increment j only when the characters at i in s and j in the dictionary word match.
  • A dictionary word is a subsequence of s if we can traverse through the entire word (i.e., j equals the length of the word) by selectively matching characters in s.

By iterating through each word in the dictionary and applying the two-pointer technique, we can check which words can be formed. During the process, we also keep track of the longest word that satisfies the condition. If multiple words have the same length, we choose the one with the lowest lexicographical order, which is the same as saying the smallest in alphabetical order.

The check function implements the two-pointer technique, and the outer loop through the dictionary selects the best candidate word according to the above-mentioned criteria.

Learn more about Two Pointers and Sorting patterns.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece：

Given an array of 1,000,000 integers that is almost sorted, except for 2 pairs of integers. Which algorithm is fastest for sorting the array?

Solution Approach

The solution implements a straightforward algorithm which utilizes the two-pointer pattern to match dictionary words against the string s. Let's break down how the Solution class achieves this:

  • The findLongestWord function is where we start, and it takes a string s and a list of strings dictionary as inputs.

  • It defines an inner function check that takes two strings a (the given string s) and b (a word from the dictionary). This function uses the two-pointer technique to determine if b can be formed from a by deletion of characters.

    • It starts with two indexes, i at 0 for string a and j at 0 for string b.
    • It iterates over the characters in a using i and only moves j forward if the characters at a[i] and b[j] match.
    • If j reaches the length of the string b, it means b is a subsequence of a, and check returns True.

  • After the check function, we have a variable ans which is initialized to an empty string. This will hold the longest string from the dictionary that can be formed.

  • The solution iterates over each word in the dictionary:

    • Using the check function, it verifies if the current word can be formed from s.
    • If it can, it then checks if the current word is longer than the one stored in ans or if it is the same length but lexicographically smaller.
    • If either condition is met, we update ans with the current word.

  • After checking all words in the dictionary, the solution returns ans, which contains the longest word that can be formed by deleting some of the given string characters, or the smallest one in lexicographical order in case there are multiple.

The use of the two-pointer technique is a key aspect of this solution as it allows for an efficient check without the need to create additional data structures or perform unnecessary computations. It is a common pattern when you need to compare or match sequences without altering their order.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

How would you design a stack which has a function min that returns the minimum element in the stack, in addition to push and pop? All push, pop, min should have running time O(1).

Example Walkthrough

Let's consider a small example to illustrate the solution approach. Assume we have the following:

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

The goal is to find the longest word from dictionary that can be formed by deleting some characters in s.

According to our algorithm:

  1. Start by iterating over each word in the dictionary. Initialize ans = "".

  2. For each word in the dictionary:

    • Call the check function to determine if the word can be formed from s.

  3. Let's start with the word "ale":

    • Initialize two pointers, i = 0 for s and j = 0 for "ale".
    • Traverse s from left to right using i and compare with j on "ale"
    • Characters match at s[0] = "a" and "ale"[0] = "a", so increment both i and j.
    • Since s[1] is "b" and doesn't match "ale"[1] ("l"), only i is incremented.
    • Continue incrementing i until we find a match for each character of "ale".
    • When j reaches the end of "ale", we know it is a subsequence of s.
    • Update ans with "ale" as it is currently the longest word found.

  4. Next, for the word "apple":

    • Repeat the same check procedure.
    • The word "apple" is also found to be a subsequence within s by matching "a", "p", "p", "l" and skipping the unused characters.
    • Since "apple" is longer than "ale", update ans with "apple".

  5. Then, check the word "monkey":

    • It is found that not all characters can be matched; thus, it is not a subsequence of s. No need to update ans.

  6. Finally, for the word "plea":

    • The check function will confirm that "plea" is a subsequence of s.
    • Since "plea" is the same length as "apple", but not lexicographically smaller, we do not update ans.

  7. After checking all words, ans contains "apple", which is the longest word that can be formed by deleting some characters from s.

The result from our example is "apple", as it is the longest word that can be created from s by deleting some characters, and it also adheres to the lexicographical order in case of length ties (even though there were none in this case).

Solution Implementation

1class Solution:
2    def findLongestWord(self, s: str, dictionary: List[str]) -> str:
3        # Helper function to check if b is a subsequence of a
4        def is_subsequence(a, b):
5            m, n = len(a), len(b)
6            pos_a = pos_b = 0
7            # Traverse both strings and check if b is subsequence of a
8            while pos_a < m and pos_b < n:
9                if a[pos_a] == b[pos_b]:
10                    pos_b += 1  # Move pointer of string b if characters match
11                pos_a += 1  # Always move pointer of string a
12            # Check if reached the end of string b, meaning b is a subsequence of a
13            return pos_b == n
14
15        # Initialize the answer to an empty string
16        longest_word = ''
17
18        # Iterate over each word in the given dictionary
19        for word in dictionary:
20            # Check if the word is a subsequence of s
21            # Update longest_word if word is longer or lexicographically smaller
22            if is_subsequence(s, word) and (len(longest_word) < len(word) or 
23                                            (len(longest_word) == len(word) and longest_word > word)):
24                longest_word = word
25        # Return the longest word that is a subsequence of s and satisfies the condition
26        return longest_word
27
1class Solution {
2
3    // Function to find the longest word in the dictionary that can be formed by deleting
4    // some characters of the given string s.
5    public String findLongestWord(String s, List<String> dictionary) {
6        String longestWord = "";
7        for (String word : dictionary) {
8            // Check if current word can be formed by deleting some characters from s
9            if (isSubsequence(s, word)) {
10                // Update longestWord if current word is longer, or the same length but lexicographically smaller
11                if (longestWord.length() < word.length() || 
12                    (longestWord.length() == word.length() && word.compareTo(longestWord) < 0)) {
13                    longestWord = word;
14                }
15            }
16        }
17        return longestWord;
18    }
19
20    // Helper method to check if string a is a subsequence of string b
21    private boolean isSubsequence(String a, String b) {
22        int i = 0; // Pointer for string a
23        int j = 0; // Pointer for string b
24        int m = a.length();
25        int n = b.length();
26
27        while (i < m && j < n) {
28            if (a.charAt(i) == b.charAt(j)) {
29                // If current characters match, move pointer j to next position in string b
30                ++j;
31            }
32            // Always move pointer i to next position in string a
33            ++i;
34        }
35      
36        // If we have traversed the entire string b, it means it is a subsequence of a
37        return j == n;
38    }
39}
40
1class Solution {
2public:
3    // Function to find the longest string in the dictionary that is a
4    // subsequence of s. If there are multiple, the smallest lexicographically
5    // will be returned.
6    string findLongestWord(string s, vector<string>& dictionary) {
7        string longestWord = ""; // Initialize the longest word to an empty string
8      
9        // Iterate over each word in the dictionary
10        for (string& word : dictionary) {
11            // Check if the word is a subsequence of s
12            // and compare it with the current longest word based on length and lexicographical order
13            if (isSubsequence(s, word) && 
14                (longestWord.size() < word.size() || 
15                (longestWord.size() == word.size() && word < longestWord))) {
16                longestWord = word; // Update the longest word
17            }
18        }
19        return longestWord; // Return the longest word
20    }
21
22    // Helper function to check if string b is a subsequence of string a
23    bool isSubsequence(string& a, string& b) {
24        int aLength = a.size(), bLength = b.size(); // Length of the strings
25        int i = 0, j = 0; // Pointers for each string
26      
27        while (i < aLength && j < bLength) {
28            // If the characters match, increment j to check the next character of b
29            if (a[i] == b[j]) ++j;
30            ++i; // Always increment i to move forward in string a
31        }
32        // String b is a subsequence of a if j has reached the end of b
33        return j == bLength;
34    }
35};
36
1function findLongestWord(s: string, dictionary: string[]): string {
2    // Sort the dictionary in descending order by word length.
3    // If two words have the same length, sort them lexicographically in ascending order.
4    dictionary.sort((word1, word2) => {
5        if (word1.length === word2.length) {
6            return word1.localeCompare(word2);
7        }
8        return word2.length - word1.length;
9    });
10
11    // Store the length of the string `s`.
12    const stringLength = s.length;
13
14    // Iterate over the sorted dictionary.
15    for (const targetWord of dictionary) {
16        // Store the length of the current target word.
17        const targetLength = targetWord.length;
18
19        // If the target word is longer than the string `s`, it cannot be formed.
20        if (targetLength > stringLength) {
21            continue;
22        }
23
24        // Initialize two pointers for comparing characters in `s` and the target word.
25        let stringPointer = 0;
26        let targetPointer = 0;
27
28        // Iterate over the characters in `s` and the target word.
29        while (stringPointer < stringLength && targetPointer < targetLength) {
30            // If the current characters match, move the target pointer to the next character.
31            if (s[stringPointer] === targetWord[targetPointer]) {
32                targetPointer++;
33            }
34            // Always move the string pointer to the next character.
35            stringPointer++;
36        }
37
38        // If all characters of the target word have been found in `s` in order,
39        // then the target word can be formed. Return it as the answer.
40        if (targetPointer === targetLength) {
41            return targetWord;
42        }
43    }
44
45    // If no word from the dictionary can be formed by `s`, return an empty string.
46    return '';
47}
48
Not Sure What to Study? Take the 2-min Quiz：

What is the worst case running time for finding an element in a binary tree (not necessarily binary search tree) of size n?

Time and Space Complexity

The given Python code defines a function findLongestWord that looks for the longest string in the dictionary that can be formed by deleting some of the characters of the string s. If there are more than one possible results, it returns the smallest in lexicographical order.

Time Complexity

Time Complexity: O(n*m + n*log(n))

Here n is the size of dictionary and m is the length of the string s.

  • The function check(a, b) has a time complexity of O(m), because in the worst case, it will check each character in string s against b.
  • This check function is called for every word in the dictionary, resulting in O(n*m).
  • Additionally, sorting the dictionary in lexicographic order is required to ensure we get the smallest word when lengths are equal. Sorting a list of strings takes O(n*log(n)*k), where k is the average length of strings; however, since we're not sorting the dictionary, we're not including this in our complexity analysis.

Space Complexity

Space Complexity: O(1)

  • No additional space is needed that grows with the input size. Only variables for iterating and comparison are used which occupy constant space.
  • Thus, the space complexity is constant since the only extra space used is for pointer variables i and j, and variable ans.

Learn more about how to find time and space complexity quickly using problem constraints.

Fast Track Your Learning with Our Quick Skills Quiz:

Which of the following problems can be solved with backtracking (select multiple)

Recommended Readings

Tech Interview Pattern | Two Pointers Introduction

Tech Interview Pattern Two Pointers Introduction If you prefer videos here's a super quick introduction to Two Pointers iframe width 560 height 315 src https www youtube com embed xZ4AfXHQ1VQ title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture allowfullscreen iframe Two pointers is a common interview technique

Sorting Summary

Sorting Summary Comparisons We presented quite a few sorting algorithms and it is essential to know the advantages and disadvantages of each one The basic algorithms are easy to visualize and easy to learn for beginner programmers because of their simplicity As such they will suffice if you don't know any advanced

LeetCode Patterns - Top Patterns for Coding Interviews

Top Patterns to Conquer the Technical Coding Interview Should the written word bore you fear not A delightful video alternative awaits iframe width 560 height 315 src https www youtube com embed LW8Io6IPYHw title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture

Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.

←
↑TA 👨‍🏫