Longest Palindrome Substring (LeetCode) solution using expandAroundCenter function, how isn't O(n^3)?

How it's not O(n^3) since inside each for loop we do 2 while loops one for len1 and other for len2 ?

The below solution is working outputs the palindrome correctly. But I am confused.

Here is the solution from LeetCode:

public String longestPalindrome(String s) {
    if (s == null || s.length() < 1) return "";

    int start = 0, end = 0;
    //Loop 1
    for (int i = 0; i < s.length(); i++) {
        //Loop 2
        int len1 = expandAroundCenter(s, i, i);

        //Loop 3
        int len2 = expandAroundCenter(s, i, i + 1);
        int len = Math.max(len1, len2);
        if (len > end - start) {
            start = i - (len - 1) / 2;
            end = i + len / 2;
        }
    }
    return s.substring(start, end + 1);
}

private int expandAroundCenter(String s, int left, int right) {
    int L = left, R = right;
    while (L >= 0 && R < s.length() && s.charAt(L) == s.charAt(R)) {
        L--;
        R++;
    }
    return R - L - 1;
}

Any idea ?

You might have got confused with expandAroundCenter running twice.

expandAroundCenter function is O(n). It is being run twice but, it is being run in sequence. So it is like O(2n) rather than O(n^2).

And as expandAroundCenter function is being called inside a for loop :
T(n) = n x 2n = 2n^2
So, time complexity is O(n^2).

The argument is quite straight forward:

• the outer loop is ∈ O(n)
• the two inner loops (calls to expandAroundCenter(...)) run in sequence, not nested. Thus, their complexity can be added up
  • for the inner loop, the worst-case scenario is that it expands from the center of the String outwards, i.e. left and right are set to n/2. In this case, the inner loop can at most iterate n/2-times since then either left < 0 or right >= n. Thus, overall the inner loop is ∈ O(n)

In total, we get O(n) (outer loop) * 2 * O(n) (inner loops in sequence) ∈ O(n^2)

Some remarks on the code:

• While possible, it is unusual in java to declare more than one variable in one line. Thus

  int start = 0, end = 0;
  

  should be

  int start = 0;
  int end = 0;
  

  This change is only code style choice and has no effect on byte code. See this post for details.

• optional braces around one-line statements should never be omitted. This can be a source of nasty bugs if we later on want to add a line and forget to include the the needed braces. Thus

  if (s == null || s.length() < 1) return "";
  

  should be re-written to

  if (s == null || s.length() < 1) {
      return "";
  }
  

• variable names should alwasy start with a lowercase letter (L -> l, R -> r).

• variables should have meaningful names. l and r are not really meaningful. Thus I propose the following refactoring:

  • renaming parameters left and right to leftStart and rightStart
  • renaming parameters l and r to currentLeft and currentRight