Table of contents
1.
Introduction
2.
Problem Statement
2.1.
Input
2.2.
Output
2.3.
Example
2.3.1.
Input
2.3.2.
Output
2.4.
Note
3.
Solution Approach
3.1.
Method 1: Brute Force Approach
3.1.1.
Java implementation
3.1.2.
Complexities
3.2.
Method 2: Manacher’s Algorithm
3.2.1.
Java implementation
3.2.2.
Complexities
4.
FAQs
5.
Key Takeaways
Last Updated: Mar 27, 2024
Easy

Prefix-Suffix Palindrome

Author Manan Singhal
0 upvote
Career growth poll
Do you think IIT Guwahati certified course can help you in your career?

Introduction

Given a string 's', we need to find whether the string has both prefix and suffix substrings of length greater than one, which is palindromes. In this article, we will find the longest string, which is a palindrome and contains two strings, a and b, as prefix and suffix, respectively.

Problem Statement

You're handed a string of lowercase English letters called s. Find the longest string, t that meets all of the following criteria:

  • The length of t is equal to or less than the length of s.
  • The string t is a palindrome.
  • There are two strings, a and b (possibly empty), such that t=a+b ("+" symbolizes concatenation), with a being the prefix and b being the suffix of s.

Input

The input consists of multiple test cases. The number of test cases is indicated on the first line by the single integer t (1≤t≤105). Now, the following t lines describe a test case.

Each test case is a string s of lowercase English characters that is not empty.

The sum of string lengths across all test cases is less than 106.

Output

Print the longest string that satisfies the given conditions for each test instance. Print any of the available solutions if there are several.

Example

Input

5
a
abcdfdcecba
abbaxyzyx
codeforces
acbba

Output

a
abcdfdcba
xyzyx
s
abba

Note

Test 1: the string s = "a" meets all criteria.

Test 2: the string "abcdfdcba" satisfies all conditions: because:

  • It has a length of 9, which is less than the length of the string s, which is 11.
  • It's a palindrome, after all.
  • "abcdfdcba" = "abcdfdc" + "ba", and "abcdfdc" is considered to be a prefix of s while "ba" is considered to be a suffix of s.

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

  1. Look for matching strings from both the front and back till the characters aren't the same.
  2. 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.
  3. 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

  1. What do you mean by palindrome string?
    Strings read the same whether we read it from forward or backward.
  2. 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.
  3. What is Manacher's Algorithm?
    Manacher's algorithm is to find out all the palindrome substrings of a given string.
  4. What is the time complexity of Manacher’s Algorithm?
    The time complexity of Manacher’s Algorithm is O(n).
  5. 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!

Live masterclass