Shortest Palindrome

Problem: Given a string , you are allowed to convert it to a palindrome by adding characters in front of it. Find and return the shortest palindrome you can find by performing this transformation.

Example:

Input: "xyzyxxx"
Output: "xxxyzyxxx"

Approach: We just need to get the longest palindrome prefix of the string say s[0...i] then (Reverse(s[i + 1....n -1] ) + s ) is our answer.

Implementation in C#:

        public string ShortestPalindrome(string s)

        {

            if (s?.Length == 0)

            {

                return string.Empty;

            }

            for (int i = s.Length - 1; i >= 0; --i)

            {

                if (this.IsPalindrome(s, 0, i))

                {

                    string prefix = s.Substring(i + 1);

                    char[] prefixArr = prefix.ToCharArray();

                    Array.Reverse(prefixArr);

                    return new string (prefixArr) + s;

                }

            }

            return string.Empty;

        }

        

        private bool IsPalindrome(string s, int startIndex, int endIndex)

        {

            while(startIndex < endIndex)

            {

                if (s[startIndex++] != s[endIndex--])

                {

                    return false;

                }

            }

            return true;

        }

Complexity: O(n^2)