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

Implementing generic Linked List with O(n) time complexity for Addition

Implementing generic linked list and performing basic operation on them with O(1) time complexity is easier than what the developers think. It's just the hype of Data Structures and the word Time Complexity.

Linked list is basically a object which holds of another object of same type and so on for every other object until the reference to next object becomes null. What is this reference? It’s just a reference variable which has an object.

To understand this better let’s take an example.

How many of you have seen Naruto? Well specific for this answer I’m going to get little less views :-D

Do you understand the word Izanmi
In this every instance which Kabuto experience is an object which hold a reference to another instance and so on until null is reached

Getting it.

Now lets move to coding example-

using System;

using System.Collections.Generic;

namespace Stucts.ADT.GenericLinkedList

{

    public class Node<T>

    {

        public T data;

        public Node<T> next = null;

    }

}

It’s a simple class which have one variable to hold data and one to hold the reference of same type of object

using System;

using System.Collections.Generic;

namespace Stucts.ADT.GenericLinkedList

{

    public class SimpleGenericLinkedList<T>

    {

        Node<T> head = null;

        Node<T> tail = null;

        private Node<T> CreateNode(T data, Node<T> next)

        {

            Node<T> newItem = new Node<T>();

            newItem.data = data;

            newItem.next = next;

            return newItem;

        }

        public void Add(T data)

        {

            if (head == null)

            {

                head = CreateNode(data, null);

                tail = head;

            }

            else {

                tail.next = CreateNode(data,null);

                tail = tail.next;

            }

        }

        public void RemoveNode(T data)

        {

            if (head.data.Equals(data))

            {

                head = head.next;

            }

            else

            {

                head.next = Remove(data, head.next);

            }

        }

        public Node<T> Remove(T data, Node<T> current)

        {

            if (current != null)

            {

                if (current.data.Equals(data))

                {

                    current = current.next;

                }

                else

                {

                    current.next = Remove(data, current.next);

                }

            }

            return current;

        }

        public void ReadAll()

        {

            Node<T> current = head;

            while (current.next != null)

            {

                Console.WriteLine(current.data); ;

                current = current.next;

            }

            Console.WriteLine(current.data); ;

        }

    }

}

Here I have performed some vary basic operation like adding, removing from head and traversing the entire list

Now to insert every new node in linked list we need to traverse through all the nodes and then add the node in the last.

Due to this traversal adding new node in linked list becomes time consuming and less effective with Time Complexity of O(n). This is clearly an issue. We can solve this by performing one very basic step while adding every node

In your Generic Linked list class add Tail node just like Head and when you add new node make it tail and keep adding new elements to tail.

SimpleGenericLinkedList<int> lnkList = new SimpleGenericLinkedList<int>();

            lnkList.Add(1);

            lnkList.Add(2);

            lnkList.Add(3);

            lnkList.Add(4);

            lnkList.Add(5);

            lnkList.Add(6);

            lnkList.Add(7);

            lnkList.Add(8);

            lnkList.Add(9);

            lnkList.Add(10);

            lnkList.RemoveNode(6);

            lnkList.ReadAll();

This is how the linked list object looks like

Just look at the object lnkList for every new node it has next and that next has another next and goes on until the lnkList.next.next….next == null;

Well that’s how linked list works and with just an easy step you can perform addition in linked list cost effective i.e. O(1)

For more content like this follow and share the blog

Thanks.