Longest Palindromic Substring

2.6K

Terminology:

Palindrome: A palindrome is a type of string that reads the same when reading left to right and right to left. An example of a palindrome can be “level”, “racecar”, “kayak” etc.

Sub-string: A string formed formed using the characters of the string that may or may not contain repetitions.

Brute Force Method:

As soon as you see the problem, the most first thought that comes to your mind would be to find all the sub-strings from the given string and keep a track of the longest one that we find. That will eventually land you to the right answer, but the time complexity of such an algorithm would be enormous. There total number of sub-strings would be =\frac{n\ *\ (n\ -\ 1)}{2}

This would cause the complexity to quickly reach O(n^2) and we can check if a string is a palindrome in O(n) time, resulting in a total complexity of O(n^3). This is something we do not want as it will take up a lot of time.

Optimized Method:

Let us try to aim for a method with a complexity of )(n^2). The algorithm will look something like:

• Start traversing the string from the first character to the last character.
• For each of the position ‘i’ in the string, find out the largest palindrome having an even length and an odd length. Note that a single letter can also be a palindrome.
• The minimum valid even length would be 2. Eg: “aa”, “cc”, xx”.
• The minimum valid odd length would be 1. Eg: “a”, “v”.
• Hence for each of the character in the string, navigate in both left and right directions till the condition for palindrome is satisfied.
• Keep a track of the largest palindrome encountered so far.
• At the end of this loop, you would have the longest palindrome sub-string.

Code:

String longestPalindrome(String str) {

    if (str.length() <= 1)
      return str;

    String LPS = "";

    for (int i = 1; i < str.length(); i++) {

      // Consider odd length
      int low = i;
      int high = i;
      // Keep extending in both left and right directions till the
      // conditions for a palindrome are met
      while(str.charAt(low) == str.charAt(high)) {
        low--;
        high++;

        // Terminating condition if we reach the end/start of the string
        if (low == -1 || high == str.length())
          break;
      }

      // Indexes low and high can be used to extract the substring
      String palindrome = str.substring(low+1, high);
      if (palindrome.length() > LPS.length()) {
        // Capture the longest palindrome found
        LPS = palindrome;
      }

      // Consider even length
      low = i - 1;
      high = i;
      while(str.charAt(low) == str.charAt(high)) {
        low--;
        high++;

        if (low == -1 || high == str.length())
          break;
      }

      palindrome = str.substring(low+1, high);
      if (palindrome.length() > LPS.length()) {
        // Similarly, keep a track of the longest even length palindrome
        LPS = palindrome;
      }
    }

    return LPS;
  }
Code language: Java (java)

Time Complexity: O(n^2)
Space Complexity: O(n)

A working solution can be found here: https://ideone.com/GvH6g0
This code can also be obtained on Github.
A similar problem is available on Leetcode.
A similar question: length of longest palindrome that can be built from a string.

Video explanation: