Longest Word in Dictionary Through Deleting — Medium Problem & Solution

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).

Difficulty: Medium
Topics: Strings, Sorting, Two Pointers
Asked at: Amazon, Google, Flipkart
Time limit: 2 s
Memory limit: 256 MB
Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

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.

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

Start with best as the empty string.
For each word, run the greedy two-pointer subsequence test against s.
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

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#, C++, Go, Java, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 282 strings problems · the whole catalogue