MAX_VALHARD- Code Anthem 1.0

editorial
1

Practice
Contest link

Setter : Ekansh Saxena
Tester : Ujjawal Gupta
Editorial : Amit_Bhardwaj

Difficulty:
Hard

Prerequisite:

Explanation & Algorithm:
Hint :
Can you think of finding the solution in the linear time using Manacher’s Algorithm?

Approach:

Since we have to find the even length LPS, we will first calculate the length of the largest possible palindrome string for every center using Manacher’s algorithm and then take the maximum plus even of them as our X.

Resource for Manacher’s Algorithm:
https://cp-algorithms.com/string/manacher.html

The steps are as follows:

First Create another string that must be the modification of S in terms of adding some special characters to make centers in between the adjacent elements. (new string = ST)
Create a vector P that will store the length of the maximum possible palindrome with center i. (where 0 <= i < N).
Create two variables C and R to store the previous center and maximum possible radius.
Run a loop from 1 to ST.length() - 1 (say, iterator = i).
Create a variable MIRR to store the possible mirror center. So, MIRR = 2 * C - i.
Check if i is less than current R then simply store the minimum of P[MIRR] and R - i into the P[i].
Now, try to expand this palindrome if the corner elements are the same.
After this update C and R accordingly.
Return Maximum element of P at the odd index/2.

Time Complexity:
O(N), Where N is the length of the given string S.

Since we are traversing each element at most two times that takes O(2*N) time and so, the overall time complexity will be O(N).

Space Complexity:
O(N), Where N is the length of the given string S.

Since we are creating an additional vector and string to hold the maximum palindrome’s length and modified S, respectively and so, the overall space complexity will be O(N).

Solution:

Setter's Code

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

int maxFXV(int n, string &s){
// Creating the new modified string.
string st = “$”;
for (auto x : s){
st.push_back(‘#’);
st.push_back(x);
}
st.push_back(‘#’);
st.push_back(‘@’);

// Array to store the length of possible palindromes.
vector<int> p(st.length());

// Variables to represents the center ('c') and radius ('r') of a palindrome.
int c = 0, r = 0;

for (int i = 1; i < st.length() - 1; i++){
    // Variable to hold the mirror center.
    int mirr = 2 * c - i;
    if (i < r){
        p[i] = min(r - i, p[mirr]);
    }

    // Try to expand the current palindrome.
    while (st[i - (1 + p[i])] == st[i + (1 + p[i])]){
        p[i]++;
    }

    // Update the current center and radius.
    if (i + p[i] > r){
        c = i;
        r = i + p[i];
    }
}

int lps = 0;
for (int i = 1; i < p.size(); i += 2){
    lps = max(lps, p[i]);
}

return lps/2;

}

void solve()
{
ll n;
cin >> n;
string s;
cin >> s;
cout << maxFXV(n, s) << endl;
}

int main()
{
ll t;
cin >> t;
while (t–)
{
solve();
}
return 0;
}