package leetcode;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

/**
 * https://leetcode.com/problems/longest-string-chain/
 */
public class Problem1048 {
    public int longestStrChain(String[] words) {
        Map<Integer, List<String>> map = new HashMap<>();
        for (String word : words) {
            if (!map.containsKey(word.length())) {
                map.put(word.length(), new ArrayList<>());
            }
            map.get(word.length()).add(word);
        }
        int answer = 0;
        Map<String, Integer> memo = new HashMap<>();
        for (String word : words) {
            answer = Math.max(answer, longestStrChain(map, word, memo) + 1);
        }
        return answer;
    }

    private static int longestStrChain(Map<Integer, List<String>> words, String word,
                                       Map<String, Integer> memo) {
        if (!words.containsKey(word.length() + 1)) {
            return 0;
        }
        if (memo.containsKey(word)) {
            return memo.get(word);
        }
        int max = 0;
        for (String s : words.get(word.length() + 1)) {
            if (isValid(word, s)) {
                max = Math.max(max, longestStrChain(words, s, memo) + 1);
            }
        }
        memo.put(word, max);
        return max;
    }

    private static boolean isValid(String word1, String word2) {
        int[] counts1 = new int[26];
        for (char c : word1.toCharArray()) {
            counts1[c - 'a']++;
        }
        int[] counts2 = new int[26];
        for (char c : word2.toCharArray()) {
            counts2[c - 'a']++;
        }
        int diff = 0;
        for (int i = 0; i < counts1.length; i++) {
            diff += Math.abs(counts2[i] - counts1[i]);
        }
        return diff == 1;
    }
}

@@ -277,22 +277,25 @@
 r, List%3C
-String
+WordCount
 %3E%3E map =
@@ -464,32 +464,167 @@
 ;%0A            %7D%0A
+            int%5B%5D count = new int%5B26%5D;%0A            for (char c : word.toCharArray()) %7B%0A                count%5Bc - 'a'%5D++;%0A            %7D%0A
             map.
@@ -646,20 +646,42 @@
 ()).add(
-word
+new WordCount(word, count)
 );%0A     
@@ -775,39 +775,118 @@
    for (
-String word
+List%3CWordCount%3E wordCounts : map.values()) %7B%0A            for (WordCount wordCount
  : word
+Count
 s) %7B%0A
+    
         
@@ -940,16 +940,21 @@
 ap, word
+Count
 , memo) 
@@ -951,32 +951,36 @@
 nt, memo) + 1);%0A
+    
         %7D%0A      
@@ -965,32 +965,42 @@
 ;%0A            %7D%0A
+        %7D%0A
         return a
@@ -1005,32 +1005,272 @@
  answer;%0A    %7D%0A%0A
+    private static class WordCount %7B%0A        private final String word;%0A        private final int%5B%5D count;%0A%0A        public WordCount(String word, int%5B%5D count) %7B%0A            this.word = word;%0A            this.count = count;%0A        %7D%0A    %7D%0A%0A
     private stat
@@ -1314,35 +1314,25 @@
 ist%3C
-String%3E%3E words, String word
+WordCount%3E%3E words
 ,%0A  
@@ -1363,24 +1363,45 @@
             
+ WordCount wordCount,
  Map%3CString,
@@ -1441,32 +1441,42 @@
 rds.containsKey(
+wordCount.
 word.length() + 
@@ -1538,24 +1538,34 @@
 containsKey(
+wordCount.
 word)) %7B%0A   
@@ -1585,24 +1585,34 @@
 rn memo.get(
+wordCount.
 word);%0A     
@@ -1654,16 +1654,22 @@
 or (
-String s
+WordCount next
  : w
@@ -1673,24 +1673,34 @@
 : words.get(
+wordCount.
 word.length(
@@ -1737,19 +1737,39 @@
 lid(word
-, s
+Count.count, next.count
 )) %7B%0A   
@@ -1824,17 +1824,20 @@
 (words, 
-s
+next
 , memo) 
@@ -1879,24 +1879,34 @@
    memo.put(
+wordCount.
 word, max);%0A
@@ -1971,285 +1971,37 @@
 lid(
-String word1, String word2) %7B%0A        int%5B%5D counts1 = new int%5B26%5D;%0A        for (char c : word1.toCharArray()) %7B%0A            counts1%5Bc - 'a'%5D++;%0A        %7D%0A        int%5B%5D counts2 = new int%5B26%5D;%0A        for (char c : word2.toCharArray()) %7B%0A            counts2%5Bc - 'a'%5D++;%0A        %7D
+int%5B%5D count1, int%5B%5D count2) %7B
 %0A   
@@ -2052,17 +2052,16 @@
  %3C count
-s
 1.length
@@ -2103,17 +2103,16 @@
 bs(count
-s
 2%5Bi%5D - c
@@ -2115,17 +2115,16 @@
  - count
-s
 1%5Bi%5D);%0A 

Update problem 1048