lundi 20 avril 2015

longest substring, time limit exceeded java

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