Longest String Chain

LeetCode Q 1048 - Longest String Chain

Given a list of words, each word consists of English lowercase letters.
Let’s say word1 is a predecessor of word2 if and only if we can add exactly one letter anywhere in word1 to make it equal to word2. For example, "abc" is a predecessor of "abac".
A word chain is a sequence of words [word_1, word_2, ..., word_k] with k >= 1, where word_1 is a predecessor of word_2, word_2 is a predecessor of word_3, and so on.
Return the longest possible length of a word chain with words chosen from the given list of words.

Example 1: Input: ["a","b","ba","bca","bda","bdca"] ; Output: 4
Explanation: one of the longest word chain is “a”,”ba”,”bda”,”bdca”.

Note:

• 1 <= words.length <= 1000
• 1 <= words[i].length <= 16
• words[i] only consists of English lowercase letters.

Solution

Code:

public int longestStrChain(String[] words) {
  Arrays.sort(words, (a, b) -> (a.length() - b.length()));

  Map<String, Integer> map = new HashMap<>();
  
  int len = words.length, max = 0;

  for (String word: words) {
    if (map.containsKey(word)) continue; // this step is important

    map.put(word, 1);

    for (int i = 0; i < word.length(); i++) {
      StringBuilder sb = new StringBuilder(word);
      String modified = sb.deleteCharAt(i);
      if (map.containsKey(modified) && map.get(modified) + 1 > map.get(word))
        map.put(word, map.get(modified) + 1);
    }

    max = Math.max(max, map.get(word));
  }

  return max;
}