Longest Word in Dictionary through Deleting

Longest Word in Dictionary through Deleting - Problem

Given a string s and a string array dictionary, return the longest string in the dictionary that can be formed by deleting some of the given string characters.

If there is more than one possible result, return the longest word with the smallest lexicographical order.

If there is no possible result, return the empty string.

Input & Output

Example 1 — Multiple Valid Words

$ Input: s = "wordgoodgoodgoodword", dictionary = ["word", "good", "goodword"]

› Output: "goodword"

💡 Note: All three words can be formed from s by deleting characters: 'word' (length 4), 'good' (length 4), 'goodword' (length 8). 'goodword' is longest.

Example 2 — Lexicographical Tie-Breaking

$ Input: s = "wordgoodgoodgoodword", dictionary = ["word", "good", "best"]

› Output: "word"

💡 Note: Both 'word' and 'good' have length 4 and can be formed. 'good' < 'word' lexicographically, so return 'good'. Wait, that's wrong. 'good' comes before 'word', so return 'good'.

Example 3 — No Valid Words

$ Input: s = "wordgoodgoodgoodword", dictionary = ["xyz", "abc"]

› Output: ""

💡 Note: Neither 'xyz' nor 'abc' can be formed as subsequences of s, so return empty string.

Constraints

1 ≤ s.length ≤ 1000
1 ≤ dictionary.length ≤ 1000
1 ≤ dictionary[i].length ≤ 1000
s and dictionary[i] consist of lowercase English letters only

Visualization

Tap to expand

Understanding the Visualization

Input

String s and dictionary of candidate words

Process

Check which words are subsequences of s

Output

Return longest word (lexicographically smallest if tie)

Key Takeaway

🎯 Key Insight: Sort dictionary to process longer words first, enabling early termination

Asked in

G Google 35 a Amazon 28 M Microsoft 22 Apple 15

The key insight is recognizing this as a subsequence matching problem. The optimal approach sorts the dictionary by length (descending) and lexicographically (ascending), then returns the first valid subsequence found. Time: O(n log n + n × m), Space: O(n).

Common Approaches

Approach	Time	Space	Notes
✓ Two Pointers - Efficient Subsequence Check	O(n × m)	O(1)	Use two pointers to efficiently check if each word is a subsequence
Brute Force - Check Every Word	O(n × m × k)	O(1)	Check each dictionary word to see if it's a subsequence of s
Sort First - Optimize Lexicographical Order	O(n log n + n × m)	O(n)	Sort dictionary by length and lexicographically, then find first valid word

Two Pointers - Efficient Subsequence Check — Algorithm Steps

For each dictionary word, initialize two pointers
Move through string s, advance word pointer on character match
Word is valid subsequence if word pointer reaches end
Track longest word with best lexicographical order

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>

bool isSubsequence(const char* word, const char* s) {
    int i = 0;
    int wordLen = strlen(word);
    for (int j = 0; s[j]; j++) {
        if (i < wordLen && word[i] == s[j]) {
            i++;
        }
    }
    return i == wordLen;
}

char* solution(char* s, char** dictionary, int dictSize) {
    char* result = malloc(1000);
    result[0] = '\0';
    
    for (int i = 0; i < dictSize; i++) {
        if (isSubsequence(dictionary[i], s)) {
            int wordLen = strlen(dictionary[i]);
            int resultLen = strlen(result);
            if (wordLen > resultLen || 
                (wordLen == resultLen && strcmp(dictionary[i], result) < 0)) {
                strcpy(result, dictionary[i]);
            }
        }
    }
    return result;
}

int main() {
    char s[1000];
    fgets(s, sizeof(s), stdin);
    s[strcspn(s, "\n")] = 0;
    
    char dictLine[10000];
    fgets(dictLine, sizeof(dictLine), stdin);
    
    char** dictionary = malloc(1000 * sizeof(char*));
    int dictSize = 0;
    
    char* token = strtok(dictLine, "[],\"\n");
    while (token != NULL && dictSize < 1000) {
        if (strlen(token) > 0) {
            dictionary[dictSize] = malloc(strlen(token) + 1);
            strcpy(dictionary[dictSize], token);
            dictSize++;
        }
        token = strtok(NULL, "[],\"\n");
    }
    
    char* result = solution(s, dictionary, dictSize);
    printf("%s\n", result);
    
    free(result);
    for (int i = 0; i < dictSize; i++) {
        free(dictionary[i]);
    }
    free(dictionary);
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n × m)

n words in dictionary, m is length of string s for each subsequence check

✓ Linear Growth

Space Complexity

O(1)

Only using pointer variables and result string

✓ Linear Space

58.2K Views

Medium Frequency

~25 min Avg. Time

1.5K Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen