Minimum size substring to be removed to make a given string palindromic

// Java program of the
// above approach
import java.util.*;

class GFG{

// Function to find palindromic
// prefix of maximum length
static String palindromePrefix(String S)
{
    int n = S.length();

    // Finding palindromic prefix of
    // maximum length
    for(int i = n - 1; i >= 0; i--) 
    {
        String curr = S.substring(0, i + 1);

        // Checking if curr subString
        // is palindrome or not.
        int l = 0, r = curr.length() - 1;
        boolean is_palindrome = true;

        while (l < r)
        {
            if (curr.charAt(l) != curr.charAt(r))
            {
                is_palindrome = false;
                break;
            }
            l++;
            r--;
        }
        
        // Condition to check if the
        // prefix is a palindrome
        if (is_palindrome)
            return curr;
    }
    
    // If no palindrome exist
    return "";
}

// Function to find the maximum size
// palindrome such that after removing
// minimum size subString
static String maxPalindrome(String S)
{
    int n = S.length();
    if (n <= 1) 
    {
        return S;
    }

    String pre = "", suff = "";

    // Finding prefix and suffix
    // of same length
    int i = 0, j = n - 1;
    while (S.charAt(i) == 
           S.charAt(j) && i < j)
    {
        i++;
        j--;
    }
    
    // Matching the ranges
    i--;
    j++;

    pre = S.substring(0, i + 1);
    suff = S.substring(j);

    // It is possible that the whole
    // String is palindrome.

    // Case 1: Length is even and
    // whole String is palindrome
    if (j - i == 1)
    {
        return pre + suff;
    }

    // Case 2: Length is odd and
    // whole String is palindrome
    if (j - i == 2)
    {
        
        // Adding that mid character
        String mid_char = S.substring(i + 1, 
                                      i + 2);

        return pre + mid_char + suff;
    }

    // Add prefix or suffix of the remaining
    // String or suffix, whichever is longer
    String rem_str = S.substring(i + 1, j);

    String pre_of_rem_str = palindromePrefix(rem_str);

    // Reverse the remaining String to
    // find the palindromic suffix
    rem_str = reverse(rem_str);
    
    String suff_of_rem_str = palindromePrefix(rem_str);

    if (pre_of_rem_str.length()    >= 
       suff_of_rem_str.length())
    {
        return pre + pre_of_rem_str + suff;
    }
    else 
    {
        return pre + suff_of_rem_str + suff;
    }
}

static String reverse(String input) 
{
    char[] a = input.toCharArray();
    int l, r = a.length - 1;
    
    for(l = 0; l < r; l++, r--) 
    {
        char temp = a[l];
        a[l] = a[r];
        a[r] = temp;
    }
    return String.valueOf(a);
}

// Driver Code
public static void main(String[] args)
{
    String S = "geeksforskeeg";
    
    System.out.print(maxPalindrome(S));
}
}

// This code is contributed by Amit Katiyar 

import java.util.ArrayList;
import java.util.Collections;

public class Main {

    // Function to compute the optimized Prefix Function of a
    // string in O(N) time
    static ArrayList<Long> prefixFunction(String s) {
        int n = s.length();
        ArrayList<Long> pi = new ArrayList<>(Collections.nCopies(n, 0L));
        for (int i = 1; i < n; i++) {
            long j = pi.get(i - 1);
            while (j > 0 && s.charAt(i) != s.charAt((int) j))
                j = pi.get((int) (j - 1));
            if (s.charAt(i) == s.charAt((int) j))
                j++;
            pi.set(i, j);
        }
        return pi;
    }

    // Function to find the length of the longest palindromic
    // prefix (or suffix) using Prefix Function
    static long longestPalindromicPrefix(String str) {
        String temp = str + '?';
        StringBuilder reversedStr = new StringBuilder(str).reverse();
        temp += reversedStr;
        int n = temp.length();
        ArrayList<Long> lps = prefixFunction(temp);
        return lps.get(n - 1);
    }

    // Function to solve the problem and print the modified string
    static void solve(String s) {
        int n = s.length();
        int i = 0, j = n - 1;

        // Find the mismatched characters from the beginning and
        // end of the string
        while (i <= j) {
            if (s.charAt(i) != s.charAt(j))
                break;
            i++;
            j--;
        }

        // If the entire string is a palindrome, no modification needed
        if (i > j) {
            System.out.println(s);
            return;
        }

        // Length of the common prefix and suffix
        int l = i;

        // Extract the substring between the mismatched characters
        StringBuilder t1 = new StringBuilder();
        for (int z = i; z <= j; z++)
            t1.append(s.charAt(z));

        // Create the reverse of the substring
        StringBuilder t2 = new StringBuilder(t1).reverse();

        // Find the length of the longest palindromic prefix and suffix
        long x = longestPalindromicPrefix(t1.toString());
        long y = longestPalindromicPrefix(t2.toString());

        // Print the modified string by removing the minimum size
        // substring to make it palindromic
        for (int k = 0; k < l; k++)
            System.out.print(s.charAt(k));

        if (x > y)
            for (int k = l; k < l + x; k++)
                System.out.print(s.charAt(k));
        else
            for (int k = (n - l) - (int) y; k < (n - l); k++)
                System.out.print(s.charAt(k));

        for (int k = (n - l); k < n; k++)
            System.out.print(s.charAt(k));

        System.out.println();
    }

    // Driver Code
    public static void main(String[] args) {
        String s = "geeksforskeeg";
        solve(s);
    }
}