Table of Contents
Introduction:
In this blog post, we’ll explore a problem from LeetCode – finding the longest palindromic substring in a given string.
A palindrome is a string that reads the same backwards as forward, such as “racecar” or “kayak“.
We’ll start with a brute-force approach, discuss its time complexity, and then move on to an optimal solution using dynamic programming.
Brute-Force Approach:
The brute-force approach to finding the longest palindromic substring involves generating all possible substrings of the input string and checking if each substring is a palindrome. Here’s the Java implementation:
import java.util.Scanner;
public class BruteForceApproach {
public static void main(String[] args) {
Scanner scan = new Scanner(System.in);
int testCases = scan.nextInt();
while (testCases -- > 0){
String str = scan.next();
System.out.println(longestPalindrome(str));
}
}
public static String longestPalindrome(String s){
if( s == null || s.length() < 1){
return "";
}
int maxLength = 0;
int startIndex = 0;
for(int i=0; i<s.length() ;i++){
for(int j = i+1; j <=s.length(); j++){
String subString = s.substring(i, j);
if(isPalindrome(subString)){
if(maxLength < j - i){
maxLength = j - i;
startIndex = i;
}
}
}
}
return s.substring(startIndex, startIndex + maxLength);
}
private static boolean isPalindrome(String str){
int left = 0;
int right = str.length() -1;
while (left < right){
if(str.charAt(left) != str.charAt(right)){
return false;
}
left++;
right--;
}
return true;
}
}
In this approach, we use two nested loops to generate all possible substrings of the input string s. For each substring, we check if it is a palindrome using the isPalindrome helper function. If the substring is a palindrome and its length is greater than the length of the current longest palindromic substring, we update the start and end indices accordingly.
Time Complexity Analysis:
The time complexity of the brute-force approach is O(n^3), where n is the length of the input string. This is because, for each character in the string, the algorithm generates all possible substrings starting from that character, and for each substring, it checks if it is a palindrome, which takes O(m) time, where m is the length of the substring. The total time complexity is O(n^2 * m), which is O(n^3) in the worst case when all characters in the string are the same.
Optimal Solution: Dynamic Programming
While the brute-force approach works for small input strings, it becomes inefficient for larger inputs due to its high time complexity. We can solve this problem more efficiently using dynamic programming. Here’s the Java implementation:
import java.util.Scanner;
public class DynamicSolution {
public static void main(String[] args) {
Scanner scan = new Scanner(System.in);
System.out.println("Enter the number of Test Cases:");
int testCases = scan.nextInt();
while (testCases -- > 0){
System.out.println("Enter the input String");
String str = scan.next();
System.out.println(longestPalindrome(str));
}
}
public static String longestPalindrome(String input){
if(input == null || input.isEmpty()){
return "";
}
int n = input.length();
boolean [][] palindromeTable = initializePalindromicTable(n);
int start = 0;
int maxLength = 0;
populatePalindromicTable(input, palindromeTable);
int [] result = findLongestPalindromicSubStringStartIndex(palindromeTable, maxLength);
start = result[0];
maxLength = result[1];
return input.substring(start, start + maxLength);
}
private static boolean[][] initializePalindromicTable(int n){
boolean [][] table = new boolean[n][n];
for(int i =0; i< n; i++){
table[i][i] = true;
}
return table;
}
private static void populatePalindromicTable(String input, boolean [][] table){
int n = input.length();
for(int len = 2; len <= n; len++){
for(int start = 0; start < n - len +1; start++){
int end = start + len - 1;
table[start][end] = input.charAt(start) == input.charAt(end) && (len == 2 || table[start+1][end-1]);
}
}
}
private static int [] findLongestPalindromicSubStringStartIndex(boolean [][] table, int maxLength){
int n = table.length;
int start = 0;
for(int len = n; len >= 1; len--){
for(int i = 0; i + len - 1 < n; i++){
if(table[i][i + len - 1]){
maxLength = len;
start = i;
break;
}
}
if(maxLength == len){
break;
}
}
return new int[]{start, maxLength};
}
}
In this approach, we construct a 2D boolean table pTable where pTable[i][j] is true if the substring from the index i to j is a palindrome, and false otherwise.
We initialize the table by setting Table[i][i] to true for all i, since substrings of length 1 are always palindromes. Then, we check substrings of length 2 and update the table accordingly.
For substrings of length 3 or more, we use a nested loop to check all possible substrings of the given length strLen. For each substring from index i to j, we check if the first and last characters of the substring are the same (s.charAt(i) == s.charAt(j)), and if the substring from i+1 to j-1 is already a palindrome (pTable[i+1][j-1] == true). If both conditions are met, we set pTable[i][j] to true and update lenOfLPS and start if the current substring is longer than the previously found longest palindromic substring.
Finally, we return the substring of s from index start to start + lenOfLPS - 1 (inclusive), which is the longest palindromic substring.
Time Complexity Analysis:
The time complexity of this dynamic programming solution is O(n^2), where n is the length of the input string. This is because the code has three nested loops: one for the length of the substring, one for the starting index, and one to check if the substring is a palindrome (which takes O(1) time due to the precomputed table).
The space complexity is O(n^2) due to the 2D boolean table pTable of size n x n.
Conclusion:
In this blog post, we discussed the LeetCode problem of finding the longest palindromic substring in a given string. We started with a brute-force approach and discussed the time complexity of O(n^3). We then introduced an optimal solution using dynamic programming, which has a time complexity of O(n^2) and a space complexity of O(n^2).
The dynamic programming solution is more efficient than the brute-force approach for larger input strings, as it avoids redundant computations by precomputing and storing the palindromic substrings in a table. However, it comes at the cost of increased space complexity.
When working with string problems, especially those from coding interview platforms like LeetCode, it’s always important to consider time and space trade-offs and choose the appropriate solution based on the constraints and requirements of the problem.
Moreover, we emphasized the importance of writing clean and maintainable code by following the principles outlined in the book “Clean Code” by Robert C. Martin. Clean code practices, such as using descriptive names, separating concerns, handling edge cases, and keeping methods small and focused, not only make our code more readable and extensible but also promote collaboration and knowledge sharing within a team.
Clean Code Principles:
- Meaningful Names: Choose descriptive and intention-revealing names for classes, methods, and variables.
- Single Responsibility Principle: Each class or method should have a single responsibility or reason to change.
- Small and Focused Methods: Keep methods small and focused on a single task, making them easy to understand and maintain.
- Handling Edge Cases: Identify and handle edge cases or exceptional situations at the beginning of the code.
- Separation of Concerns: Separate code into different classes or methods based on their responsibilities, promoting code reuse and maintainability.
By following clean code principles, such as those outlined in the book “Clean Code,” we can write code that is not only efficient but also readable, maintainable, and extensible, which is essential when solving coding problems, especially in interview settings.
