/******************************************************************************
Online Java Compiler.
Code, Compile, Run and Debug java program online.
Write your code in this editor and press "Run" button to execute it.
*******************************************************************************/
import java.util.*;
public class Main
{
public static void main(String[] args) {
System.out.println(maximumLongestWord(Set.of("string", "sring","sing", "wording", "ing", "ng", "g")));
}
public static int maximumLongestWord(Set<String> words) {
Map<String, Integer> distance = new HashMap<>();
int max = 0;
for (String word : words) {
max = Math.max(max, maximumLongestWordHelper(word, words, distance));
}
return max;
}
public static int maximumLongestWordHelper(String word, Set<String> words, Map<String, Integer> distance) {
if (distance.containsKey(word)) {
return distance.get(word);
}
if (!words.contains(word)) {
return Integer.MIN_VALUE;
}
if (word.length() == 1) {
distance.put(word, 1);
return 1;
}
int max = Integer.MIN_VALUE;
for (int i = 0; i < word.length(); i++) {
String str = word.substring(0, i) + word.substring(i + 1);
max = Math.max(max, maximumLongestWordHelper(str, words, distance));
}
if (max != Integer.MIN_VALUE) {
max++;
}
distance.put(word, max);
return max;
}
}
