Best Way To Find A Palindrome In A Given String

This post shows a trademark interview question answer along with an answer that shows an effective way to solve the puzzle.

Introduction 

 

The most famous and tricky questions asked in an interview are related to a palindrome. It's common to see questions such as the following,

• Can you check whether the given string is palindrome?
• Can you find the longest palindrome in a substring of a given string?
• Can you find all possible palindrome in a given string?

Everybody knows answers to these questions. Every developer can code the above problem statements. It's not like the interviewer is expecting that you cannot write code for these problems. He expects to see a solution that 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 the logic...

 

Consider a string ‘ssssbbssbbss’. As you can see, the longest palindrome in the substring is ‘ssbbssbbss’

 

Now let’s create the logic.

 

Step 1

 

Convert it to charArray()

Now create a table

 

If I compare a 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. Before we start comparing, remember we already have data for this. "i" has value 1 and j has valuewhich is a palindrome. So now we iterate through step 3 to find our result. After going through the 3 steps, we can say that there is a rule:

 

Rule

 

For a string to be considered as a palindrome, all its substring should be a palindrome as well.

 

Now here's how you would implement this in code.

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...

 

Conclusion 

 

I hope you find it helpful. I know there are a lot of things that I can do to make this code better. Please provide suggestions below.

 

Happy reading!