Longest Matching in Dictionary with Removals

Problem Overview

A dictionary word survives deletions from s exactly when it is a subsequence.

Intuition

A dictionary word survives deletions from s exactly when it is a subsequence. Among those, you want the longest word, and if several share that length, the lexicographically smallest. Precomputing where each letter sits in s lets every character of a word jump to its next match with binary search.

Algorithm

1Build 26 lists of indices, one per lowercase letter, by scanning s once.
2Walk the dictionary while remembering the best word so far.
3Skip a word shorter than the best, or the same length and not strictly smaller in dictionary order.
4Match the word left to right: binary search the next index strictly after the previous match.
5If every character finds such an index, replace the best word.
6Return the best word, or an empty string when nothing matched.

Example Walkthrough

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

1. ale matches at positions of a, l, and e.
2. apple is longer and also matches, so it replaces ale.
3. monkey fails because m never appears, and plea is shorter than apple.

Output: "apple"

Common Pitfalls

• Order of characters must be preserved; this is a subsequence, not an anagram.
• Equal lengths must compare the whole word, not only the first letter.
• The next match index must be strictly greater than the previous one.
• Words that cannot beat the current best should be skipped before searching.

Longest Matching in Dictionary with Removals.java

Java

// Approach: Store every index of each letter in s. A dictionary word is a
// subsequence when each next letter occurs strictly after the previous match,
// found by binary search. Keep the longest match, breaking ties by the
// lexicographically smallest word. Skip a word that cannot beat the current best.
// Complexity: O(|s| + n * L * log |s|) time, O(|s|) extra space.
import java.util.*;

class Solution {
    public String findLongestWord(String s, List<String> d) {
        List<Integer>[] pos = new ArrayList[26];
        for (int c = 0; c < 26; c++)
            pos[c] = new ArrayList<>();
        for (int i = 0; i < s.length(); i++)
            pos[s.charAt(i) - 'a'].add(i);

        String best = "";
        for (String word : d) {
            if (word.length() < best.length())
                continue;
            if (word.length() == best.length() && word.compareTo(best) >= 0)
                continue;
            if (isSubsequence(word, pos))
                best = word;
        }
        return best;
    }

    private boolean isSubsequence(String word, List<Integer>[] pos) {
        int prev = -1;
        for (int i = 0; i < word.length(); i++) {
            List<Integer> list = pos[word.charAt(i) - 'a'];
            int idx = lowerBound(list, prev + 1);
            if (idx == list.size())
                return false;
            prev = list.get(idx);
        }
        return true;
    }

    // First index whose value is >= target.
    private int lowerBound(List<Integer> list, int target) {
        int lo = 0, hi = list.size();
        while (lo < hi) {
            int mid = (lo + hi) >>> 1;
            if (list.get(mid) < target)
                lo = mid + 1;
            else
                hi = mid;
        }
        return lo;
    }
}

Was this solution helpful?