Solution Approach
Method 1: Brute Force Approach
After understanding the problem, the first solution that comes to mind is to go through the list and concatenate each word with another word to see if the string is palindrome or not. The output will be right if you use this method, and you will find the palindromic pairs.
If you take a brute force method to solve the problem, going through the complete list of words and concatenating it will eventually increase the time complexity of the solution. As a result, it will not be considered ideal.
Java implementation
import java.util.Scanner;
public class Main {
public static void main(String args[]) {
/* Taking number of test case as an input */
Scanner scn = new Scanner(System.in);
/* Storing that value in t */
int t = scn.nextInt();
/* Taking string input */
scn.nextLine();
while(t > 0) {
/* Storing the string in s */
String s = scn.nextLine();
/* Checking the given string is a palindrome or not */
if(checkPalindrome(s))
{
/* If yes, just print the string */
System.out.println(s);
}
else
{
/* i, j till palindromic nature of s */
int i = 0;
int j = s.length()-1;
/* Traversing string from start and end */
while(i <= j)
{
if(s.charAt(i) != s.charAt(j))
{
break;
}
i++;
j--;
}
/* Variables */
String ans1 = s.substring(0, i);
String ans2 = s.substring(j+1);
String ss = s.substring(i, j+1);
String ans = new String();
/* System.out.println(ans1+" "+ans2); */
/* checking the longest palindrome */
/* Variables */
i = 0;
int lMax = 0;
int ii = 0;
int jj = 0;
if(ss.length() == 2)
{
System.out.println(ans1+ss.charAt(0)+ans2);
}
else
{
while(i < ss.length()-1)
{
StringBuilder found = new StringBuilder("");
/* System.out.println(i); */
/* even length */
if(ss.charAt(i) == ss.charAt(i+1))
{
int k = i+1;
int iRef = i;
while(iRef >= 0 && k < ss.length())
{
if(ss.charAt(iRef) != ss.charAt(k))
{
break;
}
else
{
found.insert(0, ss.charAt(k));
found.insert(found.length(), ss.charAt(k));
}
k++;
iRef--;
}
if((iRef == -1 || k == ss.length()))
{
if(found.length() > lMax)
{
lMax = found.length();
ans = String.valueOf(found);
}
}
}
/* odd length */
int k = i+1;
found = new StringBuilder("");
found.insert(0, ss.charAt(i));
int iRef = i-1;
while(iRef >= 0 && k < ss.length())
{
if(ss.charAt(iRef) != ss.charAt(k))
{
break;
}
else
{
found.insert(0, ss.charAt(k));
found.insert(found.length(), ss.charAt(k));
}
k++;
iRef--;
}
if(iRef == -1 || k == ss.length())
{
if(found.length() > lMax)
{
ans = String.valueOf(found);
lMax = found.length();
}
}
i++;
}
/* If no matches print first char else print ans */
if(ans.equals(""))
{
System.out.println(s.charAt(0));
}
else
{
System.out.println(ans1+ans+ans2);
}
}
}
t--;
}
}
/* This code will check whether string s is a palindrome or not */
public static boolean checkPalindrome(String s) {
int i = 0;
int j = s.length()-1;
while(i <= j) {
if(s.charAt(i) == s.charAt(j)) {
i++;
j--;
}
else {
return false;
}
}
return true;
}
}

You can also try this code with Online Java Compiler
Run Code
Input
5
a
abcdfdcecba
abbaxyzyx
codeforces
acbba
Output
a
abcdfdcba
xyzyx
s
abba
Complexities
Time complexity
O(n3), where n is the length of the string
Reason: Three nested loops are required, so the time complexity is O(n^3).
Space complexity
O(1), where n is the length of the string
Reason: As no extra variable space is needed.
Method 2: Manacher’s Algorithm
- Look for matching strings from both the front and back till the characters aren't the same.
- The remaining strings are based on the horse-drawn carriage algorithm to obtain the longest palindrome prefix and longest palindrome suffix. Compare which is the longest.
- If no matching characters are identified in step 1, the horse-drawn carriage technique is used to extract the longest palindrome prefix and longest palindrome suffix from the original string. (Because there are character subscripts involved, the specifics are a little more).
Java implementation
import java.util.Scanner;
public class Main {
static int[] LPS;
public static void main(String[] args) {
/* Taking number of test case as an input */
Scanner scan = new Scanner(System.in);
/* Storing that value in T */
int T = scan.nextInt(); scan.nextLine();
while (T-- > 0) {
/* Taking string input */
/* Storing the string in s */
String s = scan.nextLine();
System.out.println(solve(s, s.length()));
}
}
static String solve(String s, int n) {
int i = 0, j = n-1;
while (i <= j && s.charAt(i) == s.charAt(j)) {i++; j--;}
if (i >= j) return s;
String pref = s.substring(0, i), suf = s.substring(j+1);
String s1 = s.substring(i, j+1);
String s2 = (new StringBuilder(s1)).reverse().toString();
/* Getting the largest palindrome from the given string */
String add1 = getLargestPalindromicPrefix(s1 + "?" + s2);
String add2 = getLargestPalindromicPrefix(s2 + "?" + s1);
/* Returning the largest palindrome from all the outputs */
if (add1.length() > add2.length()) return pref + add1 + suf;
else return pref + add2 + suf;
}
/* This function finds the largest palindrome from the given string */
static String getLargestPalindromicPrefix(String s) {
/* Calculating length of a string */
int n = s.length();
int[] LPS = new int[n];
int j = 0, i = 1;
/* Traversing the string */
while (i < n) {
/* If same char detected */
if (s.charAt(i) == s.charAt(j)) {
LPS[i] = j+1;
j++; i++;
} else {
if (j == 0) {
LPS[i] = 0; i++;
}
else j = LPS[j-1];
}
}
int len = LPS[n-1];
if (len > 0) return s.substring(0, len);
else return "";
}
}

You can also try this code with Online Java Compiler
Run Code
Input
5
a
abcdfdcecba
abbaxyzyx
codeforces
acbba
Output
a
abcdfdcba
xyzyx
s
abba
Complexities
Time complexity
O(n), where n is the length of the string
Reason: One nested loop is required in the function manacher, so the time complexity is O(n).
Space complexity
O(n), where n is the length of the string
Reason: Array storing n values in it.
Also read palindrome number in python.
FAQs
-
What do you mean by palindrome string?
Strings read the same whether we read it from forward or backward.
-
Is it possible for a single character to be a palindrome?
Yes, a single character is considered to be a palindrome because it reads the same from forward and backward.
-
What is Manacher's Algorithm?
Manacher's algorithm is to find out all the palindrome substrings of a given string.
-
What is the time complexity of Manacher’s Algorithm?
The time complexity of Manacher’s Algorithm is O(n).
-
What is the space complexity of Manacher’s Algorithm?
The space complexity of Manacher’s Algorithm is also O(n).
Key Takeaways
In this article, we have solved the Prefix-Suffix Palindrome (Hard version) problem using brute force and Manacher's Algorithm. We hope that this question will help you understand the string matching problems, and if you would like to learn more about Manacher’s Algorithm, check out our other articles on Manacher Algorithm.
Check out this problem - Longest Common Prefix
Attempt our Online Mock Test Series on Coding Ninjas Studio now!
Happy Coding!