Coderust: Hacking the Coding Interview/

...

/

Longest Palindromic Substring

Longest Palindromic Substring

Given a string, return the longest palindromic substring within it.

We'll cover the following...

Statement

Given a string of characters, find and return the longest palindromicA palindrome is a sequence of characters that reads the same backwards as forwards, for example, racecar. substring within the input string.

Examples

Example 1

Sample input

"bccd"

Expected output

"cc"

Example 2

Sample input

xaabacxcabaaxcabaax

Expected output

xaabacxcabaax

Try it yourself

#include <iostream>
using namespace std;
string LongestPalindromicSubstring(string s) {
	// TODO: WRITE - CODE - HERE
	return "-1";
}

Solution

There can be multiple palindromes in the input string, but we have to find the longest one.

There are two ways we can check if a string is a palindrome:

  • Start two pointers from each end of the string. Move towards the center while checking that the element at each pointer is the same.
  • Start two pointers from the center of the string. One pointer moves left, and the other moves right while checking that the element at each pointer is the same.

We use the second approach to solve our problem. We can traverse over the string, considering each position the center of a palindromic string. This way, we find each palindrome within our string and return the longest one. This center position can either be a specific character in the string (if the string size is odd) or between two characters (if the string size is even).

For example, if the string length is odd, say, “abcbaabcba ...