Longest Palindromic Substring
Given a string, return the longest palindromic substring within it.
Statement
Given a string of characters, find and return the longest
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 - HEREreturn "-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, “ ...