Can some one help me out on this algorithm time complexity? It`s a leetcode task to find the longest palindromic substring (https://leetcode.com/problems/longest-palindromic-substring/). I belive this is O(n³), but how to count this? My approach was: for loop goes s.length times (call it n), inner loop, in a worse case where string consist of equal chars, will expand the window n times, hence O(n²). But working time seems to be to big for O(n^2). Here's code:

public String longestPalindrome(String s) {
    if (s.length() == 1) {
        return s;
    }
    String max = "";
    
    for (int i = 0; i < s.length() - 1; i  ) {
        int lpointer = i;
        int rpointer = i   1;
        while (rpointer < i   3) {
            int t = rpointer;
            System.out.println(lpointer   " "   rpointer);
            while (lpointer >= 0 && rpointer < s.length() && s.charAt(lpointer) == s.charAt(rpointer)) {
                lpointer--;
                rpointer  ;
            }
            
            String temp = s.substring(lpointer   1, rpointer);
            max = max.length() < temp.length() ? temp : max;
            rpointer = t   1;
            lpointer = i;
            if (rpointer == s.length()) {
                break;
            }
        }
    }
    
    return max == "" ? String.valueOf(s.charAt(0)) : max;
}

Much appreciate any help!

CodePudding user response：

I’d say your algorithm is an O(n²) even though you have three loops:

The time-complexity of the for loop is quite easy: You have n iterations for a n long string. The inner while loops are a bit more complex: I noticed that outside the inner while loop the both cursers have always the difference from 1 or 2. I guess that’s because you want to check for even and uneven palindromes. That means that the inner while loop is only running twice for every iteration of the for loop. In addition, the inner while loop can max run the half the length of the string because it searches in both directions. This leads to both while loops having a complexity of 2 * n/2 which equals n. So n*n leads to O(n²).

Still, besides the time-complexity, your code runs very slow (>700ms) compared to the average submissions. With some optimization I was able to reproduce an O(n²) algorithm with only 15ms running time. It uses pretty much your attempt. The only major difference is that instead of having the two inner while loops to differentiate between even and uneven numbers it uses two different separate loops:

public static String longestPalindrome(String s) {
    if (s.length() <= 0) return "";
    char[] chars = s.toCharArray();
    int longest = 0;
    int iLongest = 0;
    for (int i = 0; i < chars.length; i  ) { //position to start from 
        if (longest == chars.length || (chars.length - 1 == longest && ((chars.length % 2 != 0 && longest % 2 == 0) || i - 1 > longest / 2))) break; //skip useless iterations
        //uneven
        for (int j = 0; j <= (chars.length - 1 - i < i ? chars.length - 1 - i : i); j  ) { //max length possible in both directions
            if (chars[i j] == chars[i-j]) {
                int nLongest = j*2 1;
                if (nLongest > longest) {
                    longest = nLongest;
                    iLongest = i;
                }
            } else break;
        }
        //even
        for (int j = 0; j <= (chars.length - 1 - i < i ? chars.length - 1 - i : i - 1); j  ) {
            if (chars[i j] == chars[i-j-1]) {
                int nLongest = (j 1)*2;
                if (nLongest > longest) {
                    longest = nLongest;
                    iLongest = i;
                }
            } else break;
        }
    }
    int start = iLongest - ((longest % 2 == 0 ? longest : longest - 1) / 2);
    int stop = iLongest   ((longest - 1) / 2);
    return s.substring(start, stop   1);
}

Hope that answeres your question.