Create a Palindrome in the Shortest Length

[BloomS]

You are given a string s. You can convert s to a
palindrome
by adding characters in front of it.

Return the shortest palindrome you can find by performing this transformation.

*Example 1:

Input: s = "aacecaaa"
Output: "aaacecaaa"

Example 2:

Input: s = "abcd"
Output: "dcbabcd"

Constraints:

    0 <= s.length <= 5 * 104

s consists of lowercase English letters only.

[pritikumari]

class Solution {
public:
string shortestPalindr ome(string s) {

}
};

[kanchansaini123]

Suppose we have a string s. We can convert it to palindrome by adding characters in front of it. We have to find the shortest palindrome, that we can find performing this information. So if the string is like “abcc”, then the result will be − "ccbabcc".

To solve this, we will follow these steps −

n := size of s, s1 := s, s2 := s

Reverse the string s2

s2 := s concatenate "#" concatenate s2

Define an array lps of size same as s2

j := 0, i := 1

while i < size of s2, do −

if s2[i] is same as s2[j], then,

lps[i] := j + 1

increase i by 1, increase j by 1

Otherwise

if j > 0, then, j := lps[j - 1]

Otherwise increase i by 1

extra := substring of s from lps[size of s – 1] to n - lps[size of lps - 1])

Reverse extra

return extra concatenate s

Example:-
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
string shortestPalindr ome(string s) {
int n = s.size();
string s1 = s;
string s2 = s;
reverse(s2.begi n(), s2.end());
s2 = s + "#" + s2;
vector <int> lps(s2.size());
int j = 0;
int i = 1;
while(i <s2.size()){
if(s2[i] == s2[j]){
lps[i] = j + 1;
j++;
i++;
} else {
if(j > 0){
j = lps[ j - 1];
} else {
i++;
}
}
}
string extra = s.substr(lps[lps.size() - 1], n - lps[lps.size() - 1]);
reverse(extra.b egin(), extra.end());
return extra + s;
}
};
main(){
Solution ob;
cout << (ob.shortestPal indrome("abcc") );
}