Given a string, find the length of the longest substring without repeating characters. For example, the longest substring without repeating letters for "abcabcbb" is "abc", which the length is 3. For "bbbbb" the longest substring is "b", with the length of 1.
public static int lengthOfLongestSubstring(String s) {
if (s.length()==0)
return 0;
int maxlen = 1;
HashMap<Character, ArrayList<Integer>> check = new HashMap<Character,ArrayList<Integer>>();
for (int i = 0; i < s.length(); i++) {
for (int j = i; j < s.length(); j++) {
if (!check.containsKey(s.charAt(j))) {
ArrayList<Integer> value= new ArrayList<>();
value.add(j);
check.put(s.charAt(j), value);
}
else {
maxlen = Math.max(j - i, maxlen);
ArrayList<Integer> temp = check.get(s.charAt(j));
i=temp.get(temp.size()-1);
// get the last index(biggest index) of the key value
check.clear();
break;
}
if(j==s.length()-1) {
maxlen = Math.max(j - i + 1, maxlen);
}
}
}
return maxlen;
}
}
For the last test of long repeatable string, time limit exceeded. Do not know how to optimize. seek for improvement, thanks
Aucun commentaire:
Enregistrer un commentaire