Longest Dictionary Word | Dataford Interview Questions

Your question is Longest Dictionary Word. Start with the requirements on the right.

Run and submit as often as you like. When you're ready, talk me through your approach or go straight to the code.

Problem

Avathon's AI platform receives compacted text labels from an edge pipeline. Given a source string and a dictionary, return the longest dictionary word that can be formed by deleting zero or more characters from the source while preserving character order.

If multiple words have the maximum length, return the lexicographically smallest one. If no dictionary word can be formed, return an empty string.

Formal Specification

Implement longest_dictionary_word(source, dictionary).

source is a lowercase English string.
dictionary is a list of lowercase English words.
Return one dictionary word as a string.
A word is formable when it is a subsequence of source. Characters do not need to be contiguous, and each source character can be used at most once.

To support large inputs, preprocess the source so each next-character lookup is efficient. Avoid comparing every candidate by repeatedly scanning the source from its beginning.

Constraints

1 <= len(source) <= 100000
1 <= len(dictionary) <= 100000
The total number of characters across dictionary words is at most 1000000
All characters are lowercase English letters
Dictionary entries may be duplicated

Function Signature

def longest_dictionary_word(source, dictionary):