← All posts

Algorithms / Find Palindrome

When solving palindrome problems, we need to avoid sliding window solution (a.k.a brute force), where we try to generate every substring and check to find the palindrome.

The good approach to go for is the expandable solution.

For each character in the string, start expanding to the left and right of the character and check if each s[left] and s[right] pair are the same, if they’re, expand the length of the palindrome string we found.

One thing we need to be aware of is, there are two cases of a palindrome:

• Odd length palindrome: which will be centered at a character, for example:

  abcba
    ^
  

• Even length palindrome: which will be centered in the middle of the two adjacent characters

  abba
   ^^
  

The algorithm to expand and find the palindrome is pretty easy to implement:

expand(s: string, l: int, r: int) -> int {
  while (l >= 0 && r < s.length() && s[l] == s[r]) {
    l--;
    r++;
  }
  return r - l - 1;
}

We use the l and r to mark the left and right boundary of the substring we want to check, if the pair are matched, we expand l to the left and r to the right until we reached the boundaries or the pair doesn’t matched anymore.

Eventually, we return the length of the substring we found r - l - 1.

Now, whenever we want to check if a string is palindrome or not, we perform two check, one for the odd length palindrome, and another one for the even length palindrome:

Let’s say we’re at position #2, there are two strings we should check:

0 1 2 3 4 5
a b c c b d
    ^
 
   i = 2
 odd = expand(s, i, i) // centered at c
even = expand(s, i, i + 1) // centered between c and c

Given the length len of a palindrome substring, and the center of it, we can easily calculate the start and end point of that substring:

start = center - (len - 1) / 2;
end = center + len / 2;

Now that we have the algorithm to find palindrome centered at a character, here’ the algorithm to find longest palindrome substring of a string:

int start = 0; int end = 0;
for (int i = 0; i < s.length(); i++) {
  int odd = expand(s, i, i);
  int even = expand(s, i, i + 1);
  int len = max(odd, even);
  if (len > end - start) {
    start = i - (len - 1) / 2;
    end = i + len / 2;
  }
}
return s.substr(start, end - start + 1);

---