We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Longest Word in Dictionary through Deleting

Number: 524

Difficulty: Medium

Paid? No

Companies: Google

Problem Description

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

Key Insights

  • Use a two pointers technique to determine if a word is a subsequence of s.
  • Compare valid words by length; in case of ties, use lexicographical order.
  • Iterating over each word in the dictionary allows handling constraints efficiently.
  • The subsequence check is linear with respect to the length of s.

Space and Time Complexity

Time Complexity: O(n * s) where n is the number of words in the dictionary and s is the length of string s. Space Complexity: O(1) extra space, apart from the output.

Solution

Iterate through each word in the dictionary and use a two-pointers approach to confirm if it is a subsequence of s. For each valid word, update the answer if the word has a greater length than the current best or if it has the same length but is lexicographically smaller. This method ensures that after checking all the dictionary words, the best possible match is returned.

Code Solutions

# Python solution using two pointers
class Solution:
    def findLongestWord(self, s: str, dictionary: List[str]) -> str:
        def is_subsequence(word: str) -> bool:
            i = 0  # Pointer for s
            for char in word:
                while i < len(s) and s[i] != char:
                    i += 1
                if i == len(s):
                    return False
                i += 1
            return True

        best = ""
        for word in dictionary:
            # Check if word is a subsequence of s
            if is_subsequence(word):
                # Update best if the word is longer or lexicographically smaller when lengths are equal
                if len(word) > len(best) or (len(word) == len(best) and word < best):
                    best = word
        return best
← Back to All Questions