Longest Word in Dictionary Through Deleting Problem

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.

Examples

Example 1:

1
2
3
4

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

Example 2:

1
2
3
4

Input:
s = "abpcplea", dictionary = ["a","b","c"]
Output:
 "a"

Solution

Method 1 – Two Pointers and Subsequence Check

Intuition

The main idea is to check for each word in the dictionary if it is a subsequence of the given string. If multiple words are valid, we return the longest one, and if there is a tie, the lexicographically smallest one.

Approach

  1. Iterate through each word in the dictionary.
  2. For each word, use two pointers to check if it is a subsequence of the given string.
  3. Track the longest valid word found so far. If two words have the same length, choose the lexicographically smaller one.
  4. Return the answer after checking all words.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

class Solution {
public:
    string findLongestWord(string s, vector<string>& d) {
        string ans = "";
        for (auto& w : d) {
            int i = 0, j = 0;
            while (i < s.size() && j < w.size()) {
                if (s[i] == w[j]) j++;
                i++;
            }
            if (j == w.size()) {
                if (w.size() > ans.size() || (w.size() == ans.size() && w < ans)) ans = w;
            }
        }
        return ans;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

func findLongestWord(s string, d []string) string {
    ans := ""
    for _, w := range d {
        i, j := 0, 0
        for i < len(s) && j < len(w) {
            if s[i] == w[j] {
                j++
            }
            i++
        }
        if j == len(w) {
            if len(w) > len(ans) || (len(w) == len(ans) && w < ans) {
                ans = w
            }
        }
    }
    return ans
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

class Solution {
    public String findLongestWord(String s, List<String> d) {
        String ans = "";
        for (String w : d) {
            int i = 0, j = 0;
            while (i < s.length() && j < w.length()) {
                if (s.charAt(i) == w.charAt(j)) j++;
                i++;
            }
            if (j == w.length()) {
                if (w.length() > ans.length() || (w.length() == ans.length() && w.compareTo(ans) < 0)) ans = w;
            }
        }
        return ans;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

class Solution {
    fun findLongestWord(s: String, d: List<String>): String {
        var ans = ""
        for (w in d) {
            var i = 0; var j = 0
            while (i < s.length && j < w.length) {
                if (s[i] == w[j]) j++
                i++
            }
            if (j == w.length) {
                if (w.length > ans.length || (w.length == ans.length && w < ans)) ans = w
            }
        }
        return ans
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

class Solution:
    def findLongestWord(self, s: str, d: list[str]) -> str:
        ans = ""
        for w in d:
            i = j = 0
            while i < len(s) and j < len(w):
                if s[i] == w[j]:
                    j += 1
                i += 1
            if j == len(w):
                if len(w) > len(ans) or (len(w) == len(ans) and w < ans):
                    ans = w
        return ans
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

impl Solution {
    pub fn find_longest_word(s: String, d: Vec<String>) -> String {
        let mut ans = String::new();
        for w in d.iter() {
            let (mut i, mut j) = (0, 0);
            let s_bytes = s.as_bytes();
            let w_bytes = w.as_bytes();
            while i < s_bytes.len() && j < w_bytes.len() {
                if s_bytes[i] == w_bytes[j] { j += 1; }
                i += 1;
            }
            if j == w_bytes.len() {
                if w.len() > ans.len() || (w.len() == ans.len() && w < &ans) {
                    ans = w.clone();
                }
            }
        }
        ans
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

class Solution {
    findLongestWord(s: string, d: string[]): string {
        let ans = "";
        for (const w of d) {
            let i = 0, j = 0;
            while (i < s.length && j < w.length) {
                if (s[i] === w[j]) j++;
                i++;
            }
            if (j === w.length) {
                if (w.length > ans.length || (w.length === ans.length && w < ans)) ans = w;
            }
        }
        return ans;
    }
}

Complexity

  • ⏰ Time complexity: O(n * m), where n is the number of words in the dictionary and m is the length of the string s, since for each word we may scan all of s.
  • 🧺 Space complexity: O(1), as only a few variables are used for tracking the answer.

Method 2 – Sorting and Subsequence Check

Intuition

By sorting the dictionary by length (descending) and lexicographically (ascending), we can return the first word that is a subsequence of the given string, which guarantees the correct answer.

Approach

  1. Sort the dictionary by length (descending) and lexicographically (ascending).
  2. For each word, check if it is a subsequence of the given string using two pointers.
  3. Return the first valid word found.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

class Solution {
public:
    string findLongestWord(string s, vector<string>& d) {
        sort(d.begin(), d.end(), [](const string& a, const string& b) {
            return a.size() > b.size() || (a.size() == b.size() && a < b);
        });
        for (auto& w : d) {
            int i = 0, j = 0;
            while (i < s.size() && j < w.size()) {
                if (s[i] == w[j]) j++;
                i++;
            }
            if (j == w.size()) return w;
        }
        return "";
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

import "sort"
func findLongestWord(s string, d []string) string {
    sort.Slice(d, func(i, j int) bool {
        if len(d[i]) != len(d[j]) {
            return len(d[i]) > len(d[j])
        }
        return d[i] < d[j]
    })
    for _, w := range d {
        i, j := 0, 0
        for i < len(s) && j < len(w) {
            if s[i] == w[j] {
                j++
            }
            i++
        }
        if j == len(w) {
            return w
        }
    }
    return ""
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

class Solution {
    public String findLongestWord(String s, List<String> d) {
        d.sort((a, b) -> b.length() != a.length() ? b.length() - a.length() : a.compareTo(b));
        for (String w : d) {
            int i = 0, j = 0;
            while (i < s.length() && j < w.length()) {
                if (s.charAt(i) == w.charAt(j)) j++;
                i++;
            }
            if (j == w.length()) return w;
        }
        return "";
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

class Solution {
    fun findLongestWord(s: String, d: List<String>): String {
        val sorted = d.sortedWith(compareByDescending<String> { it.length }.thenBy { it })
        for (w in sorted) {
            var i = 0; var j = 0
            while (i < s.length && j < w.length) {
                if (s[i] == w[j]) j++
                i++
            }
            if (j == w.length) return w
        }
        return ""
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

class Solution:
    def findLongestWord(self, s: str, d: list[str]) -> str:
        d.sort(key=lambda x: (-len(x), x))
        for w in d:
            i = j = 0
            while i < len(s) and j < len(w):
                if s[i] == w[j]:
                    j += 1
                i += 1
            if j == len(w):
                return w
        return ""
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

impl Solution {
    pub fn find_longest_word(s: String, mut d: Vec<String>) -> String {
        d.sort_by(|a, b| b.len().cmp(&a.len()).then(a.cmp(b)));
        for w in d.iter() {
            let (mut i, mut j) = (0, 0);
            let s_bytes = s.as_bytes();
            let w_bytes = w.as_bytes();
            while i < s_bytes.len() && j < w_bytes.len() {
                if s_bytes[i] == w_bytes[j] { j += 1; }
                i += 1;
            }
            if j == w_bytes.len() {
                return w.clone();
            }
        }
        String::new()
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

class Solution {
    findLongestWord(s: string, d: string[]): string {
        d.sort((a, b) => b.length - a.length || a.localeCompare(b));
        for (const w of d) {
            let i = 0, j = 0;
            while (i < s.length && j < w.length) {
                if (s[i] === w[j]) j++;
                i++;
            }
            if (j === w.length) return w;
        }
        return "";
    }
}

Complexity

  • ⏰ Time complexity: O(n * m + n log n), where n is the number of words in the dictionary and m is the length of the string s, due to sorting and checking subsequences.
  • 🧺 Space complexity: O(n), for sorting the dictionary.