# Java Hashing Solution

• We simply maintain a map of all subsequence frequencies and get the subsequence with frequency 1 that has longest length.

NOTE: This solution does not take advantage of the fact that the optimal length subsequence (if it exists) is always going to be the length of some string in the array. Thus, the time complexity of this solution is non-optimal. See https://discuss.leetcode.com/topic/85044/python-simple-explanation for optimal solution.

``````public int findLUSlength(String[] strs) {
Map<String, Integer> subseqFreq = new HashMap<>();
for (String s : strs)
for (String subSeq : getSubseqs(s))
subseqFreq.put(subSeq, subseqFreq.getOrDefault(subSeq, 0) + 1);
int longest = -1;
for (Map.Entry<String, Integer> entry : subseqFreq.entrySet())
if (entry.getValue() == 1) longest = Math.max(longest, entry.getKey().length());
return longest;
}

public static Set<String> getSubseqs(String s) {
Set<String> res = new HashSet<>();
if (s.length() == 0) {
return res;
}
Set<String> subRes = getSubseqs(s.substring(1));
for (String seq : subRes) res.add(s.charAt(0) + seq);
return res;
}
``````

• My idea is the same, but I used bitmasks for listing subsequences in my solution

• Firstly, find all string's subsequence, use map<subsequence, counts>, when counts== 1, find the longest length of string

``````public class Solution {
public int findLUSlength(String[] strs) {
Map<String, Integer> map = new HashMap<>();
for(String s : strs) add(s, map);
int max = -1;
for(String s : map.keySet()) {
//only counts == 1, means not repeat
if(map.get(s) == 1) max = Math.max(max, s.length());
}
return max;
}
void add(String s, Map<String, Integer> map) {
int largest = (int)Math.pow(2, s.length());
//2^n-1 sequence
for(int i = 1; i < largest; i++) {
StringBuilder sb = new StringBuilder();
int j = i, k = s.length() - 1;
while(j > 0) {
if((j & 1) == 1) sb.append(s.charAt(k));
j = (j >>> 1);
k--;
}
//subsequence
String temp = sb.reverse().toString();
//if exists, count ++
map.put(temp, map.getOrDefault(temp, 0) + 1);
}
}
}
``````

• Another Approach.

``````public int findLUSlength(String[] strs) {
Map<String, Boolean> map = new HashMap<>();
for (String str : strs) {
if (map.containsKey (str)) map.put (str, false);
else map.put (str, true);
}

for (Iterator<Map.Entry<String, Boolean>> entryIterator = map.entrySet().iterator(); entryIterator.hasNext();) {
Map.Entry<String, Boolean> entry = entryIterator.next();

if (entry.getValue()) {
for (Map.Entry<String, Boolean> innerEntry : map.entrySet()) {
if (!innerEntry.getValue() && isSubSequence (innerEntry.getKey(), entry.getKey())) {
entry.setValue(false);
break;
}
}
}
}

int max = -1;
for (Map.Entry<String, Boolean> entry : map.entrySet())
if (entry.getValue()) max = Math.max (max, entry.getKey().length());
return max;
}

private boolean isSubSequence (String s, String t) {
int tidx = 0;
for (int sidx = 0; sidx < s.length() && tidx < t.length(); sidx ++)
if (s.charAt(sidx) == t.charAt(tidx)) tidx ++;
return tidx >= t.length();
}
``````

• The time complexity is `O(n 2^k)`, where `k` is the length of string. Am I wrong?

• Share my java solution with clear comments.
First sort by length (longest to shortest) and ignore all the duplicated string, check every potential string and return the str that is not a subsequnce of the longer ones

``````    public int findLUSlength(String[] strs) {
Map<Integer, Set<String>> map = new HashMap<>();//length -> Set<String>
Set<String> duplicate = new HashSet<>();//record all duplicated String, they will not in the result
int maxLen = 0;//the max length of string

for (String str : strs) {
int size = str.length();
maxLen = Math.max(maxLen, size);

Set<String> set = map.get(size);
if (set == null) {
set = new HashSet<>();
map.put(size, set);
}
}
}

List<String> longer = new ArrayList<>();//record all the strings that is previously visited in the following loop(longer or equal to the lenght of the cur string)
for (int i = maxLen; i >= 0; i--) {
if (map.get(i) == null) {//ignore unused length
continue;
}

Set<String> set = map.get(i);

for (String str : set) {
if (!duplicate.contains(str)) {//duplicated String will not in the final result
boolean flag = true;//potential string, flag it as true

for (String longerStr : longer) {
//check if the potential string is one of its previously visited strs' subsequence
if(isSubsequence(longerStr, str)) {
flag = false;
break;
}
}

if (flag) {
return i;
}
}
}
}

return -1;
}

//if yes, then b is subsequence of a
private boolean isSubsequence(String a, String b) {//assuming length of a >= length of b
if (a.length() == b.length()) {//this corner check is unnecessary actually
return a.equals(b);
}

int i = 0;
int j = 0;
while (i < a.length() && j < b.length()) {
if (a.charAt(i) == b.charAt(j)) {
i++;
j++;
} else {
i++;
}
}
if (j == b.length()) {
return true;
}
return false;
}
}
``````

• @Hellokitty_2015 I have the same idea as yours! And here is my version:

``````class Solution {
public int findLUSlength(String[] strs) {
if (strs == null || strs.length < 1) {
return -1;
}
if (strs.length == 1) {
return strs[0].length();
}
Arrays.sort(strs, (a, b) -> (b.length() - a.length()));
Map<String, Integer> map = new HashMap<>();
Set<String> failStrings = new HashSet<>();
for (String str : strs) {
map.put(str, map.getOrDefault(str, 0) + 1);
}
for (String str : strs) {
if (map.get(str) == 1 && !failStrings.contains(str)) {
boolean goodToGo = true;
for (String failString : failStrings) {
if (failString.length() != str.length() && isSub(failString, str)) {
goodToGo = false;
break;
}
}
if (goodToGo) {
return str.length();
}
} else {
}
}
return -1;
}

private boolean isSub(String main, String cand) {
int index = 0;
for (int i = 0; i < main.length(); ++i) {
if (main.charAt(i) == cand.charAt(index)) {
++index;
}
if (index == cand.length()) {
return true;
}
}
return index == cand.length();
}
}
``````

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