Monday, June 10, 2013

Find the longest palindrome in a given string (C#)

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
namespace ConsoleApplication1
{
    class Program
    {
        static void Main(string[] args)
        {
            string str = "paliniladrome";
            string longestPalindrome = GetMaxPalindromeString(str);
            Console.WriteLine(longestPalindrome);
            Console.ReadKey();
          
        }
        public static string GetMaxPalindromeString(string testingString)
        {
            int stringLength = testingString.Length;
            int maxPalindromeStringLength = 0;
            int maxPalindromeStringStartIndex = 0;
            for (int i = 0; i < stringLength; i++)
            {
                int currentCharIndex = i;
                for (int lastCharIndex = stringLength - 1; lastCharIndex > currentCharIndex; lastCharIndex--)
                {
                    if (lastCharIndex - currentCharIndex + 1 < maxPalindromeStringLength)
                    {
                        break;
                    }
                    bool isPalindrome = true;
                    if (testingString[currentCharIndex] != testingString[lastCharIndex])
                    {
                        continue;
                    }
                    else
                    {
                        int matchedCharIndexFromEnd = lastCharIndex - 1;
                        for (int nextCharIndex = currentCharIndex + 1; nextCharIndex < matchedCharIndexFromEnd; nextCharIndex++)
                        {
                            if (testingString[nextCharIndex] != testingString[matchedCharIndexFromEnd])
                            {
                                isPalindrome = false;
                                break;
                            }
                            matchedCharIndexFromEnd--;
                        }
                    }
                    if (isPalindrome)
                    {
                        if (lastCharIndex + 1 - currentCharIndex > maxPalindromeStringLength)
                        {
                            maxPalindromeStringStartIndex = currentCharIndex;
                            maxPalindromeStringLength = lastCharIndex + 1 - currentCharIndex;
                        }
                        break;
                    }
                }
            }
            if (maxPalindromeStringLength > 0)
            {
                return testingString.Substring(maxPalindromeStringStartIndex, maxPalindromeStringLength);
            }
            return null;
        }
    }
}
  

1 comment:

Unknown said...

This is a very nice approach, albeit a little complex to follow and could be optimized.

However, I pasted the code and it ran without any issues and passed with flying colors! Very well done! :)