Java hashmap O(n^2) solution beats 98%


  • 5
    J

    The basic idea is use an array of hashmap to record which substring repeated how many time up until current index, and another String array record the longest repeated substring up until current index. Then start from the end build the string and recursively do that for substring. Also, we have a global hashmap to record computed results for better performance. There are some edge cases need to be considered:

    1. "abab" should not replace "ab" as the longest repeated substring
    2. If there is an overlap for two different repeated substring, you should choose the longest one, for example "abcdefabcdefffff", you should let the middle 'f' belong to 'abcdef' instead of 'fffff'.
            int n = s.length();
            HashMap[] reps = new HashMap[n];
            String[] words = new String[n];
            int bound = -1;
            for (int i = 0; i < n; i++) {
                reps[i] = new HashMap<String, Integer>();
                words[i] = "";
                for (int j = i; j >= 0; j--) {
                    String tmp = s.substring(j, i + 1);
                    if (j > 0 && reps[j - 1].containsKey(tmp)) {
                        if (j - 1 > bound || tmp.length() >= words[bound].length()) {
                            reps[i].put(tmp, (int)reps[j - 1].get(tmp) + 1);
                        } else {
                            reps[i].put(tmp, 1);
                        }
                        if (tmp.split(words[i]).length > 0) {
                            words[i] = tmp;
                            bound = i;
                        }
                    } else {
                        reps[i].put(tmp, 1);
                    }               
                }
            }
            
            StringBuilder sb = new StringBuilder();
            for (int i = n - 1; i >= 0; i--) {
                if (words[i].length() > 0 && words[i].length() * (int)reps[i].get(words[i]) > 4) {
                    sb.insert(0, (int)reps[i].get(words[i]) + "[" + encode(words[i]) + "]");
                    i = i - words[i].length() * (int)reps[i].get(words[i]) + 1;
                } else {
                    sb.insert(0, s.charAt(i));
                }
            }
            
            return sb.toString();
    

  • 2
    M

    May I ask a quick question here? I am not sure

    String tmp = s.substring(j, i + 1);
    

    if this line is O(1). If it is O(n), then the overall complexity would be O(n^3).


Log in to reply
 

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