Site icon Study Algorithms

Longest Palindromic Substring

Let us suppose that we are given a string ‘str’. You need to find out the longest palindrome as a substring. Note that the elements of the string should be contagious.

Example 1:
Input: "aaebabad"
Output: "bab"
Note: "aba" is also a valid answer

Example 2:
Input: "cbeereed"
Output: "eeree"

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:

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:

Exit mobile version