# java solution using TreeMap (17 ms)

• My idea for this problem:
for example, we have following input: "aabbcc", "aabbcc", "bcc", "bc"

1. using TreeMap<Integer,List<String>> (key is the length of string):
deal with the input into: 6 : aabbcc , aabbcc
3: bcc
2: bc
2. sort all of the values (List<String>) using CompareTo
3. find the candidate which can be the final result from every list:
word indexed i can be a candidate if it is not equals to the two words indexed i-1 and i+1;
4. make sure if this candidate is the final result:
compare this candidate to all of the words which is longer than it, if it is not a subsequence to any longer words, this word is the final result.

My solution is quit complex, if you have some better idea, please post your solution. Thanks~

``````public class Solution {
public int findLUSlength(String[] strs) {
if(strs == null || strs.length == 0) {
return -1;
}
TreeMap<Integer,List<String>> map = new TreeMap<Integer,List<String>>();
for(int i = 0; i < strs.length; i++) {
if(map.containsKey(strs[i].length())) {
}else {
List<String> list = new ArrayList<String>();
map.put(strs[i].length(), list);
}
}
List<Integer> lenlist = new ArrayList<Integer>();
for(Map.Entry<Integer,List<String>> entry : map.entrySet()) {
List<String> list = entry.getValue();
Collections.sort(list, new Comparator<String>() {
public int compare(String s1, String s2) {
if(s1.compareTo(s2) < 0) {
return -1;
}else {
return 1;
}
}
});
}
return helper(map, lenlist);
}

protected int helper(TreeMap<Integer,List<String>> map, List<Integer> lenlist) {
for(int i = lenlist.size() - 1; i >= 0; i--) {
List<String> wordlist = map.get(lenlist.get(i));
for(int j = 0; j < wordlist.size(); j++) {
if(iscandidate(j, wordlist)) {
if(i == lenlist.size()-1) {
return lenlist.get(i);
}else {
int p = i+1;
List<String> templist = new ArrayList<String>();
while(p < lenlist.size()) {
p++;
}
boolean tag = false;
for(String s : templist) {
if(issubstr(s, wordlist.get(j))) {
tag = true;
break;
}
}
if(!tag) {
return wordlist.get(j).length();
}
}
}
}
}
return -1;
}

protected boolean iscandidate(int index, List<String> wordlist) {
if(wordlist.size() == 1) {
return true;
}
if(index == 0) {
return !wordlist.get(0).equals(wordlist.get(1));
}else if(index == wordlist.size() - 1) {
return !wordlist.get(index-1).equals(wordlist.get(index));
}else {
return !wordlist.get(index-1).equals(wordlist.get(index)) && !wordlist.get(index).equals(wordlist.get(index+1));
}
}

protected boolean issubstr(String s1, String s2) {
int p = 0;
for(int i = 0; i < s1.length(); i++) {
if(p == s2.length()) {
return true;
}
if(s1.charAt(i) == s2.charAt(p)) {
p++;
}
}
return p == s2.length();
}
}``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.