How to write return who letters you should remove to make string palindrome?

Question

Like in question, exercise if it is possible to create a palindromic string of minimum length 3 characters by removing 1 or 2 characters. For example string "abjchba", we can remove letters "jc" and will get palindromic, in this case program should return removed letters so "jc". I know that we can mke palindromic by removing also "ch" but in exercise is that we should remove characters that appear earlier in string. Program should always attempt to create the longest palindromic substring. I wrote methods to reverse String and method to check that string is palindromic:

private static String reverse(String string) {
        return new StringBuilder(string).reverse().toString();
    }

private static boolean isPalin(String string) {
        return string.equals(reverse(string));
    }

I also made method to create Palindromic to return symbols we should remove to make palindromic, but beacuse i'm working on sb 'temp' I got exception . Have anyone idea how to fix it and finish exercise?

private static String createPalindrome(String str) {
        StringBuilder result = new StringBuilder();
        StringBuilder temp = new StringBuilder(str);
        for (int i = 0; i < str.length(); i++) {
            if (str.charAt(i) == str.charAt(str.length() - 1 - i)){
                continue;
            }else {
                result.append(str.charAt(i));
                temp.deleteCharAt(i);
                if (isPalin(temp.toString())){
                    return result.toString();
                }
            }
        }
        return "not possible";
    }

Answer 1

Method 1:

1. Find longest palindromic subsequence(LPS)

Given string: "abjchba"

Longest Palindrome Subsequence: "abhba". Others like "abjba" and "abcba" also are LPS but you want to remove chars that appear earlier so that "abhba".

If (input string length - length of LPS) > 2, return "not possible".

2. Remove letters from the input string that are not in the LPS.

Start matching string with LPS. 'j' and 'c' won't match. Add them to result and return.

Method 2:

1. Find longest common subsequence (LCS) between input string and its reverse.

   String: "abjchba"

   Reverse: "abhcjba"

   LCS: Take "abhba" in our case

If (input string length - length of LCS) > 2, return "not possible".

2. Step 2 will be the same as that of in Method 1 above.

As you are trying for at most 2 deletions, I am thinking if we can do better with time complexity.

Answer 2

I think the simplest way to fix your code is to use recursion. When you find a char that does not match, remove it and call recursively.

// Helper function to remove a character from a string
public static String removeAt(String s, int i)
{
    return s.substring(0, i) + s.substring(i + 1);
}
private static String createPalindromeRecursive(String str) {
    // Only need to check half the string
    for (int i = 0, j = str.length() - 1; i < j; i++, j--) {
        // if (something) continue; else {} <- the else is not needed
        //     because the continue skips to the end of the loop
        // or you can negate the condition and don't use continue
        if (str.charAt(i) == str.charAt(j)){
            continue;
        }
        String temp = createPalindrome(removeAt(str, i));
        // Success. Return the new string
        if (null != temp) return temp;
        else return null;
    }
    return str;
}
private static String createPalindrome(String str) {
    String palindrome = createPalindromeRecursive(str);
    if (palindrome == null || palindrome.length() < str.length() - 2) {
        return "not possible";
    }
    else {
        return palindrome;
    }
}

Answer 3

using System;
using System.Text;

class MainClass
{

    public static String removeAt(String s, int i)
    {
        return s.Substring(0, i) + s.Substring(i + 1);
    }
    private static String createPalindromeRecursive(String str)
    {
        for (int i = 0, j = str.Length - 1; i < j; i++, j--)
        {
            if (str[i] == str[j])
            {
                continue;
            }
            String temp = PalindromeCreator(removeAt(str, i));
            if (null != temp) return temp;
            else return null;
        }
        return str;
    }
    public static string PalindromeCreator(string str)
    {

        String palindrome = createPalindromeRecursive(str);
        StringBuilder result = new StringBuilder();
        StringBuilder temp = new StringBuilder(str);
        if (palindrome == null || palindrome.Length < str.Length - 2)
        {
            return "not possible";
        }
        else
        {

            for (int i = 0; i < str.Length; i++)
            {
                if (str[i] == str[(str.Length - 1 - i)])
                {
                    continue;
                }
                else
                {
                    result.Append(str[i]);
                    temp.Remove(i, str.Length);
                    return result.ToString();
                }
            }
            return palindrome;
        }
    }

    static void Main()
    {
        // keep this function call here
        Console.WriteLine(PalindromeCreator(Console.ReadLine()));
    }

}