CODEWITHSUNDEEP
algorithmpriority-queuepalindrome
alessiop86
alessiop86

Reputation: 1305

What's the running time of this "compute all palindrome substrings" algorithm?

   public PriorityQueue<String> findPalindromesSubstring(String string) {
        PriorityQueue<String> palindromes = new PriorityQueue<>();
        string = string.replace("","#");
        for (int i = 0; i < string.length(); i++) { //n iterations
            int j = 0;
            while (i-j >= 0 && i+j < string.length() && string.charAt(i-j) == string.charAt(i+j)) {
                String palindrome = string.substring(i-j, i+j+1);
                if (palindrome.charAt(0) != '#') {
                    palindromes.add(palindrome.replace("#", ""));
                }
                j++;
            }

        }
        return palindromes;
    }

I used a PriorityQueue because I need the palindrome substrings sorted alphabetically. At the moment I don't care about duplicates, but I am not sure about the worst case running time the result, from my understanding it is something like

n (chars in string because of for loop)

*

n (max possible length of a palindrome because of inner while loop/2)

*

log(max number of palindromes because of PriorityQueue's add operation)

So the running time is O(n^2*logn) ? Or should I replace one of the n with something else?

Upvotes: 0

Views: 128

Answers (1)

Adam Stawicki
Adam Stawicki

Reputation: 106

Running time complexity is O(N^3*log(N^2)).
Let's take a closer look at palindromes.add(palindrome.replace("#", "")); replace function takes O(n), add function makes O(lg N^2) comparisons (because we have at most N^2 palindromes, so height of heap is lg N^2). Each comparison of a string takes O(N) so total time of this line is O((log N^2) * N + N)

Upvotes: 1

Related Questions