CODEWITHSUNDEEP
c++stringoptimization
Giuseppe
Giuseppe

Reputation: 492

What is the worst-case running time for this algorithm?

I'm studying some code for my Facebook interview. I understand what this algorithm does, but I can't figure out its complexity. This is what's stated on a website I've visited:

Since expanding a palindrome around its center could take O(N) time, the overall complexity is O(N^2).

Could someone explain to me how they got that running time, specifically the average and worst cases?

The problem given is to find the largest palindrome substring. I'm kind of new to strings.

I also want to know if you guys think I should learn Manacher’s Algorithm, which is O(N). It's a better solution that uses less memory, but it's really hard for me to understand.

string expandAroundCenter(string s, int c1, int c2) {
  int l = c1, r = c2;
  int n = s.length();
  while (l >= 0 && r <= n-1 && s[l] == s[r]) {
    l--;
    r++;
  }
  return s.substr(l+1, r-l-1);
}

string longestPalindromeSimple(string s) {
  int n = s.length();
  if (n == 0) return "";
  string longest = s.substr(0, 1);  // a single char itself is a palindrome
  for (int i = 0; i < n-1; i++) {
    string p1 = expandAroundCenter(s, i, i);
    if (p1.length() > longest.length())
      longest = p1;

    string p2 = expandAroundCenter(s, i, i+1);
    if (p2.length() > longest.length())
      longest = p2;
  }
  return longest;
}

Upvotes: 1

Views: 1093

Answers (1)

Olayinka
Olayinka

Reputation: 2845

Read Big O notation and Analysis of algorithms and a little bit of this, then come back and see if the rest of my answer makes sense.

I'd check with an O(n) algorithm if the string itself is a palindrome before going ahead.

Let's see, you have a for loop that runs n times, at each iteration, you call a function that runs ... well, the worst possible case is that you always find the longest possible palindrome every time you call expandAroundCenter i.e the iteration runs until l < 0 || r > n-1. This implies that the algorithm is O(min(i, n-i)). Now if we find the sum from 1 to n of min(i, n-i), we get this, which is of O(n²).

Upvotes: 1

Related Questions