Split string into two longest palindrome

Question

So I have this string "nmmaddammhelloollehdertr", if we split the string into x = "nmmaddamm" and y = "helloollehdertr" we could find the LPS to be x = "mmaddamm" and y = "helloolleh". We know that this is the biggest palindrome as x has a length of 8, and y has a length of 10. 10 * 8 = 80

I attempted this problem by using dynamic programming with Longest Palindromic Subsequence, noting that I need to split the string at a pivot point creating two strings with the longest size.

A brute-force approach was to try every single palindrome for each subsequence, and that was my attempt:

using System;

namespace Palindrome
{
    class Program
    {
        static void Main(string[] args)
        {
            Console.WriteLine(GetLongestPalindrome("nmmaddammhelloollehdertr"));
        }

        static int GetLongestPalindrome(string s)
        {
            int longest = 1;
            for (int i = 0; i < s.Length; ++i)
                longest = Math.Max(longest, GetLongestPalindromeHelper(s.Substring(0, i)) * GetLongestPalindromeHelper(s.Substring(i)));
            return longest;
        }

        static int GetLongestPalindromeHelper(string str)
        {
            if (str.Length == 0)
                return 1;

            /*
             * For a str = "madeam"
             *       || 0 | 1 | 2 | 3 | 4 | 5 ||
             *  _____|| m | a | d | e | a | m ||
             * | 0 m || 1 | 1 | 1 | 1 | 1 |_5_||
             * | 1 a || 0 | 1 | 1 | 1 |_3_| 3 ||
             * | 2 d || 0 | 0 |_1_| 1 | 1 | 1 ||
             * | 3 e || 0 | 0 | 0 | 1 | 1 | 1 ||
             * | 4 a || 0 | 0 | 0 | 0 | 1 | 1 ||
             * | 5 m || 0 | 0 | 0 | 0 | 0 | 1 ||
             * 
             */
            int[,] matrix = new int[str.Length, str.Length];

            // i -> row
            // j -> column
            // windowSize -> the numbers of chars in the window

            // each character is a palindrome with a length 1
            for (int i = 0; i < str.Length; ++i)
                matrix[i, i] = 1;

            // we handled windowSize 1, so we start at 2
            for (int windowSize = 2; windowSize <= str.Length; ++windowSize)
            {
                for (int i = 0, j = windowSize - 1; i < str.Length - windowSize + 1; ++i, j = i + windowSize - 1)
                {
                    if (str[i] == str[j])
                        matrix[i, j] = matrix[i + 1, j - 1] + 2;
                    else
                        matrix[i, j] = Math.Max(matrix[i, j - 1], matrix[i + 1, j]);
                }
            }

            return matrix[0, str.Length - 1];
        }
    }
}

However, I am sure there is a better way to do this, but I do not know how. Any advice? Also, anyone could point out what the complexity of my code is?

Thanks!

Answer 1

You can do Manacher's Algorithm in Linear time and get the length of all the palindromes. After that, you can process the length to get the maximum length from left and from right, and then with one final loop, you can get your answer.
The total complexity will be O(n).
There are many helpful resources for Manacher's Algorithm including these links: good explanation, Animation

static void Main(String[] args) {
    string s = "nmmaddammhelloollehdertr";
    long ans = Manacher(s, s.Length);
    Console.WriteLine(ans);
}
static long Manacher(string s, int N) {
    int i, j, k, rp;
    int[,] R = new int[2, N + 1];
    // rp is the palindrome radius
    // R is a table for storing results (2 rows for even and odd length palindromes)

    // store the maximum length of the palindromes from left and from right here
    int[] MaxFromLeft = new int[N];
    int[] MaxFromRight = new int[N];
    for (i = 0; i < N; i++) {
        MaxFromLeft[i] = 1;
        MaxFromRight[i] = 1;
    }

    // insert guards to iterate easily 
    // without having to check going out of index range
    s = "@" + s + "#";

    for (j = 0; j <= 1; j++) {
        R[j, 0] = rp = 0; i = 1;
        while (i <= N) {
            while (s[i - rp - 1] == s[i + j + rp]) rp++;
            R[j, i] = rp;
            k = 1;
            while ((R[j, i - k] != rp - k) && (k < rp)) {
                R[j, i + k] = Math.Min(R[j, i - k], rp - k);
                k++;
            }
            rp = Math.Max(rp - k, 0);
            i += k;
        }
    }

    s = s.Substring(1, N);

    int len     // length of the palindrome
        , st    // start index
        , end;  // end index;
    for (i = 1; i <= N; i++) {
        for (j = 0; j <= 1; j++)
            for (rp = R[j, i]; rp > 0; rp--) {
                len = 2 * rp + j;
                st = i - rp - 1;
                end = st + len - 1;
                // update the maximum length
                MaxFromRight[st] = Math.Max(MaxFromRight[st], len);
                MaxFromLeft[end] = Math.Max(MaxFromLeft[end], len);
            }
    }

    // get the accumulative maximums 
    // to avoid doing a second loop inside
    for (i = N - 2, j = 1; i > 1; i--, j++) {
        MaxFromRight[i] = Math.Max(MaxFromRight[i], MaxFromRight[i + 1]);
        MaxFromLeft[j] = Math.Max(MaxFromLeft[j], MaxFromLeft[j - 1]);
    }

    long ans = 0;
    for (i = 0; i < N - 1; i++) {
        ans = Math.Max(ans, MaxFromLeft[i] * MaxFromRight[i + 1]);
    }
    return ans;
}