Longest Palindromic Substring (LPS) Editorial

Practice Problem Link: Longest Palindromic Substring (LPS)

Please make sure to try solving the problem yourself before looking at the editorial.

Problem Statement

Given a string, return the longest palindromic substring (LPS) in it.

Note: There can be multiple palindromic substrings with the max length. In case of conflict, return the substring that has the smallest starting index.

Naive Approach

A simple solution is to consider every substring of the given string and find the palindromic substring having the maximum length. This can be done by running three loops. The two outer loops to consider each substring and the inner loop to check if the substring is palindromic or not.

Analysis

• Time Complexity: O(n3)
• Auxiliary Space Complexity: O(1)

Implementation

C++

string lps(string str) {
    int n = str.size();
	string palindrome;
	for (int i = 0; i < n; i++) {
		for(int j = i; j < n; j++) {
			int start = i, end = j, isPalindromic = 1;
			while(start <= end) {
				if (str[start++] != str[end--]) {
					isPalindromic = 0;
				}
			}
			if (isPalindromic == 1 && j - i + 1 > palindrome.size()) 
			palindrome = str.substr(i, j - i + 1);
		}
	}
	return palindrome;
}

Java

class Solution {
	String lps(String str) {
	    int n = str.length();
		String palindrome = "";
		for (int i = 0; i < n; i++) {
			for(int j = i; j < n; j++) {
				int start = i, end = j, isPalindromic = 1;
				while(start <= end) {
					if (str.charAt(start++) != str.charAt(end--)) {
						isPalindromic = 0;
					}
				}
				if (isPalindromic == 1 && j - i + 1 > palindrome.length()) 
				palindrome = str.substring(i, j + 1);
			}
		}
		return palindrome;
	}
}

Optimal Approach

The optimal approach to this problem is based on dynamic programming.

Let's say isPalindromic[i][j] denotes whether the substring from the index i to j is palindromic or not. To check if it is palindromic we can simply check isPalindromic[i + 1][j - 1] (i.e. the substring from index i + 1 to j - 1 is palindromic or not) and compare the characters at the index i and j.

The idea is to fill the isPalindromic table in a bottom-up manner using the above mentioned DP state. If substring from index i to j is palindromic then assign isPalindromic[i][j] as true otherwise false.

Note: There are two base cases that need to be handled separately.

• Case 1: If i = j, isPalindromic[i][j] will always be true as a substring of unit length is always palindromic.
• Case 2: If j - i = 1(i.e substring of length two), isPalindromic[i][j] will be true only if str[i] and str[j] are equal.

Analysis

• Time Complexity: O(n2)
• Auxiliary Space Complexity: O(n2)

Implementation

C++

string lps(string str) {
    int n = str.size();
	int isPalindromic[n][n];
	int start = 0, palindromicLength = 1;
	for(int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
	        if (i == j) {
				isPalindromic[i][j] = 1;
			} else if (j - i == 1 && str[j] == str[i]) {
				isPalindromic[i][j] = 1;
				if(palindromicLength != 2) {
					start = i;
					palindromicLength = 2;
				}
			} else {
				isPalindromic[i][j] = 0;
			}
		}
	}
	for (int i = n - 3; i >= 0; i--) {
		for(int j = i + 2; j < n; j++) {
			if (isPalindromic[i + 1][j - 1] == 1 && str[i] == str[j]) {
				isPalindromic[i][j] = 1;
				if (palindromicLength <= j - i + 1) {
					start = i;
					palindromicLength = j - i + 1;
				}
			}
		}
	}
	return str.substr(start, palindromicLength);
}

Java

class Solution {
	String lps(String str) {
	    int n = str.length();
		int[][] isPalindromic = new int[n][n];
		int start = 0, palindromicLength = 1;
		for(int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++) {
				if (i == j) {
					isPalindromic[i][j] = 1;
				} else if (j - i == 1 && str.charAt(j) == str.charAt(i)) {
					isPalindromic[i][j] = 1;
					if(palindromicLength != 2) {
						start = i;
						palindromicLength = 2;
					}
				} else {
					isPalindromic[i][j] = 0;
				}
			}
		}
		for (int i = n - 3; i >= 0; i--) {
			for(int j = i + 2; j < n; j++) {
				if (isPalindromic[i + 1][j - 1] == 1 && str.charAt(i) == str.charAt(j)) {
					isPalindromic[i][j] = 1;
					if (palindromicLength <= j - i + 1) {
						start = i;
						palindromicLength = j - i + 1;
					}
				}
			}
		}
		return str.substring(start, start + palindromicLength);
	}
}