Longest Word in Dictionary Through Deleting

Medium
640.

Longest Word in Dictionary Through Deleting

Longest Word in Dictionary Through Deleting is a medium coding problem on strings, sorting and two pointers, asked in Amazon, Google and Flipkart interviews.

Given a string s and a dictionary of strings, return the longest dictionary word that can be formed by deleting some characters of s (a subsequence).

If several words tie on length, return the lexicographically smallest one. If none can be formed, return the empty string.

Example 1

Input
s = "codekairo", dictionary = ["code","cairo","dek","kai"]
Output
cairo
Explanation
"code" and "cairo" are both subsequences of length 4 and 5; the longest is "cairo".

Example 2

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

Example 3

Input
s = "abc", dictionary = ["xyz"]
Output
Explanation
Nothing can be formed.

Constraints

  • 1 <= s.length <= 1000
  • 1 <= dictionary.length <= 1000
  • 1 <= dictionary[i].length <= 1000
  • All strings consist of lowercase English letters.
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {string} s
 * @param {string[]} dictionary
 * @return {string}
 */
var findLongestWord = function(s, dictionary) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Longest Word in Dictionary Through Deleting — Solution

Longest Word in Dictionary Through Deleting solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript.

Longest Word in Dictionary Through Deleting is a medium coding problem on strings, sorting and two pointers, asked in Amazon, Google and Flipkart interviews.

Problem statement

Given a string s and a dictionary of strings, return the longest dictionary word that can be formed by deleting some characters of s (a subsequence).

If several words tie on length, return the lexicographically smallest one. If none can be formed, return the empty string.

Example 1

Input: s = "codekairo", dictionary = ["code","cairo","dek","kai"]
Output: cairo
Explanation: "code" and "cairo" are both subsequences of length 4 and 5; the longest is "cairo".

Example 2

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

Example 3

Input: s = "abc", dictionary = ["xyz"]
Output: 
Explanation: Nothing can be formed.

Constraints

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

Hints for Longest Word in Dictionary Through Deleting

  1. Hint 1

    Subsequence testing is the same two-pointer walk as ever.

  2. Hint 2

    There is no need to sort: keep a running best and replace it only on a strictly longer word, or an equal-length word that compares smaller.

  3. Hint 3

    Comparing strings with < is lexicographic in every target language.

How to solve Longest Word in Dictionary Through Deleting

Test each dictionary word for being a subsequence of s, and keep a running champion under the ordering the statement defines: longer wins, and on a tie the lexicographically smaller wins.

Approach

  1. Start with best as the empty string.
  2. For each word, run the greedy two-pointer subsequence test against s.
  3. If it passes and is longer than best, adopt it; if it passes and ties on length but compares smaller, adopt it too.

Why it works

The comparison rule is a strict total order on the candidates, so scanning once while keeping the maximum under that order finds the unique answer — no sort required.

Complexity

  • Time — O(|s| · total dictionary length)
  • Space — O(1) beyond the answer

Pitfalls

  • Adopting on >= length without the lexicographic tie-break returns whichever equal-length word came last.
  • Sorting the dictionary first works but costs an unnecessary log n factor.
  • The empty string is the correct answer when nothing matches — not -1 or a null.

Reference solution

Python

from typing import List

def findLongestWord(s: str, dictionary: List[str]) -> str:
    def is_sub(w: str) -> bool:
        i = 0
        for c in s:
            if i < len(w) and c == w[i]:
                i += 1
        return i == len(w)
    best = ""
    for w in dictionary:
        if not is_sub(w):
            continue
        if len(w) > len(best) or (len(w) == len(best) and w < best):
            best = w
    return best

Java

public static String findLongestWord(String s, String[] dictionary) {
    String best = "";
    for (String w : dictionary) {
        int i = 0;
        for (int j = 0; j < s.length() && i < w.length(); j++) {
            if (s.charAt(j) == w.charAt(i)) i++;
        }
        if (i != w.length()) continue;
        if (w.length() > best.length() || (w.length() == best.length() && w.compareTo(best) < 0)) best = w;
    }
    return best;
}

C++

string findLongestWord(string s, vector<string>& dictionary) {
    string best = "";
    for (const string& w : dictionary) {
        size_t i = 0;
        for (size_t j = 0; j < s.size() && i < w.size(); j++) {
            if (s[j] == w[i]) i++;
        }
        if (i != w.size()) continue;
        if (w.size() > best.size() || (w.size() == best.size() && w < best)) best = w;
    }
    return best;
}

JavaScript

var findLongestWord = function(s, dictionary) {
    var isSub = function(w) {
        var i = 0;
        for (var j = 0; j < s.length && i < w.length; j++) {
            if (s.charAt(j) === w.charAt(i)) i++;
        }
        return i === w.length;
    };
    var best = "";
    for (var t = 0; t < dictionary.length; t++) {
        var w = dictionary[t];
        if (!isSub(w)) continue;
        if (w.length > best.length || (w.length === best.length && w < best)) best = w;
    }
    return best;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 515 strings problems · the whole catalogue

Learn the technique: Strings · Sorting Algorithms