How to find palindrome in a given string (Effective way)

Finding longest palindrome in a substring of a given string

Most famous and tricky question asked in a interview are related to palindrome

1.  Check whether the given string is palindrome? 
2.  Find the longest palindrome in a substring of a given string?
3.  Find all possible palindrome in given string?

These are the common question asked around palindrome.

Everybody knows answers to these questions. Every developer can code the above problem statements.
Its not like interviewer is expecting that you cannot write code for these problems. He expects to see a solution which is fast and robust. That’s where you get an edge.

There are several ways to do this and all are correct. I am showing one of them which I think is more performance oriented and robust.

So, let’s proceed with logic

Consider a string ‘ssssbbssbbss’ as you can see easily that longest palindrome substring is ‘ssbbssbbss’

Now let’s create a logic

Step 1:

Convert it to charArray()

Now create a table

if I compare character at location 0 with 0 it will give me true

similarly, for 1,1 | 2,2 | 3,3, | and so on

let’s fill the table

Step 2:

Now start comparing characters with 0 to 1, 1 to 2, 2 to 3 and so on and fill the table

Now our basic record is generated. This will come handy later

Step 3:

Now will start comparing characters that are at least 2 indices apart and so one until first and last character and we keep filling this table until the very last column and reuse the same data

If we start comparing character at index 0 with character at index 2

Int i = 0; Int j = 2;

i.e. if arr[i] == arr[j]

after this add 1 in i and subtract 1 from j

and before we start comparing remember we already have data for this
Yes, i has value 1 and j has value 1 which is a palindrome and we already know that.

So we iterating through the step 3 and we’ll find our result.

Now after going through there 3 steps we can say that there is a rule

Rule

              For a string to be considered as palindrome, all it’s substring should be palindrome as well.

Now how’d you implement this in code.
Here it is –

public class Palindrome

{

       private string value;

       private int Length = 0;

       int[,] table = null;

       char[] s = null;

       public int stringLength = 0;

       public int minCount = 0;

       public Palindrome(string palindromeString)

       {

              value = palindromeString;

              Length = value.Length;

              table = new int[Length, Length];

              s = value.ToCharArray();

              Initialize();

       }

       private void Initialize()

       {

              for (int i = 0; i < Length; i++)

              {

                     table[i, i] = 1; 

                     if (i != Length - 1)

                     {

                            if (s[i] == s[i + 1])

                            {

                                   table[i, i + 1] = 1;

                            }

                            else {

                                 table[i, i + 1] = -1;

                            }

                      }

              }

       }

       public string FindLongestPalindromInString()

       {

              for (int i = 0; i < Length; i++)

              {

                    for (int j = i+2; j < Length; j++)

                    {

                          table[i, j] = FindAllPalindrome (i, j);

                          if (table[i, j] == 1 && j-i > stringLength)

                          {

                                 stringLength = j-i;

                                 minCount = i;

                          }

                    }

               }

               return value.Substring(minCount, (stringLength)+1);

       }

       private int FindAllPalindrome(int p, int q)

       {

             int result = 0;

             if (table[p, q] == 1)
            {
                  result = 1;
            }

             else if (table[p, q] == -1)

             {

                    result = -1;

             }

             else

             {

                    if (s[p] == s[q])

                    {

                          result = FindAllPalindrome(p + 1, q - 1);

                    }

                    else { result = -1; }

             }

             return result;

       }

}

Here's the result

I hope you find it helpful.
I know there are lot of things which I can do to make this code better.

Happy reading (ta-ta).