Longest Palindromic Substring:

e.g. 1-) abacxyyxcf

       Sol-) cxyyxc 

      2-) abacxyydxcf 

       Sol-) aba 

1- Approach :  The Naive approach to this problem is of 0(n^3) using three for loops. So to optimize the complexity we fill follow up this approach. The idea here is, that we will iterate over each character in the given string and check whether it is forming a palindrome with its adjacent characters or not. If it is forming a palindrome  we will check for next adjacent characters forming palindrome and will consider palindrome with maximum length. Now palindrome can be formed of even as well as odd size. So we will consider both the cases alongside and choose the best of them.

O(n^2) time | O(1) space

________________________________________________________________________________

#include <iostream>

#include <vector>

#include <string>

using namespace std;

void print(string str, int strt, int end){

    for(int i=strt;i<end;i++){

        cout << str[i];

    }

}

vector <int> getLongestPalindromicSubstring(string str, int leftIdx, int rightIdx){

    while(leftIdx >= 0 && rightIdx < str.size()){

        if(str[leftIdx] != str[rightIdx]){

            break;

        }

        leftIdx--;

        rightIdx++;

    }

    return {leftIdx + 1, rightIdx}; // returning indexes in the same form to compare maximum length palindrome.

starting substring at leftIdx + 1 and ending at rightIdx - 1.

}

void longestPalindromicSubstring(string str){

    vector<int> longest = {0,1}; // first character is a palindrome of length 1 i.e.(1-0)

[0,1) ----> indexing done this way just to get proper

length of substring.(0-including 1-excluding).

    for(int i = 1; i < str.size(); i++){

        vector<int> currLongest;

        vector <int> odd = getLongestPalindromicSubstring(str, i-1, i+1); // odd length palindrome

        vector <int> even = getLongestPalindromicSubstring(str, i-1, i); // even length palindrome

        // Considering palindrome with maximum length between even and odd palindrome if found

        if(odd[1]-odd[0] > even[1]-even[0]){

            currLongest.push_back(odd[0]);

            currLongest.push_back(odd[1]);

        }

        else{

            currLongest.push_back(even[0]);

            currLongest.push_back(even[1]);

        }

// Considering palindrome with maximum length between current and longest palindrome found till

        if(currLongest[1]-currLongest[0] > longest[1]-longest[0]){

            longest[0] = currLongest[0];

            longest[1] = currLongest[1];

        }

    }

// Printing Longest Palindromic Substring

    print(str, longest[0], longest[1]);

}

int main() {

    string s;

    cin >> s;

    longestPalindromicSubstring(s);   

    

    return 0;

}

________________________________________________________________________________

2- Approach : Manacher's Algorithm-->

O(n) time | O(1) space

________________________________________________________________________________

#include <bits/stdc++.h> using namespace std; #define SIZE 100000 + 1 int P[SIZE * 2]; // Transform S into new string with special characters inserted. string convertToNewString(const string &s) { string newString = "@"; for (int i = 0; i < s.size(); i++) { newString += "#" + s.substr(i, 1); } newString += "#$"; return newString; } string longestPalindromeSubstring(const string &s) { string Q = convertToNewString(s); int c = 0, r = 0; // current center, right limit for (int i = 1; i < Q.size() - 1; i++) { // find the corresponding letter in the palidrome subString int iMirror = c - (i - c); if(r > i) { P[i] = min(r - i, P[iMirror]); } // expanding around center i while (Q[i + 1 + P[i]] == Q[i - 1 - P[i]]){ P[i]++; } // Update c,r in case if the palindrome centered at i expands past r, if (i + P[i] > r) { c = i; // next center = i r = i + P[i]; } } // Find the longest palindrome length in p. int maxPalindrome = 0; int centerIndex = 0; for (int i = 1; i < Q.size() - 1; i++) { if (P[i] > maxPalindrome) { maxPalindrome = P[i]; centerIndex = i; } } cout << maxPalindrome << "\n"; return s.substr( (centerIndex - 1 - maxPalindrome) / 2, maxPalindrome); } int main() { string s = "kiomaramol\n"; cout << longestPalindromeSubstring(s); return 0; }

________________________________________________________________________________