LeetCode #5: Longest Palindromic Substring (Solution) Read it later

When it comes to solving complex coding challenges, finding the optimal solution is crucial. In this article, we’ll delve into the LeetCode problem of finding the longest palindromic substring, and explore an efficient solution using dynamic programming. We’ll break down the problem step by step and provide you with an easily understandable code example in C++.

Understanding the Problem

Given a string, our task is to identify the longest palindromic substring within it. A palindromic string reads the same forwards as it does backward. For instance, “racecar” and “madam” are palindromic strings. However, our goal is to uncover the longest palindromic substring from the given string. This means that the identified substring should be a palindrome and have the maximum possible length.

Did you know that the 3Sum Problem from LeetCode is a commonly asked question in Google interviews? If you’re interested in practicing your problem-solving skills, why not try your hand at the 3Sum Problem?

Approach 1: Brute Force

While a straightforward approach would involve generating all possible substrings and checking each one for palindromicity, this method is highly inefficient due to its exponential time complexity. Therefore, let’s explore a smarter approach that employs dynamic programming.

Approach 2: Dynamic Programming

Before delving into the dynamic programming solution, let’s establish a prerequisite concept – the Longest Common Subsequence (LCS).

Longest Common Subsequence (LCS): LCS refers to the longest sequence of characters that two given strings have in common. For instance, consider two strings: “abcde” and “ace.” Their LCS is “ace,” which has a length of 3.

Key Insight: To find the longest palindromic substring, we can use the concept of LCS in an innovative way. We’ll take the given string, create a copy of it, and then reverse the original string. Next, we’ll determine the LCS of these two strings, the original and its reverse.

Why do this? Because the longest palindromic substring of a string is essentially the LCS of the string and its reverse!

Dynamic Programming Algorithm

1. We’ll use a function lcs to calculate the LCS of two strings.
2. Initialize two vectors prev and cur, both with sizes m+1 (length of the second string).
3. For each character in the first string, iterate through characters in the second string.
4. If the characters match, update cur[ind2] as 1 + prev[ind2-1], else update it as max(prev[ind2], cur[ind2-1]).
5. Update prev to be the same as cur after each iteration of the outer loop.
6. Return prev[m] as the LCS.

Finding the Longest Palindromic Substring

1. Take the input string and its reverse.
2. Calculate the LCS of these two strings using the lcs function.
3. Return the length of the LCS, which is the length of the longest palindromic substring.

Code Example in C++

#include <bits/stdc++.h>
using namespace std;

int lcs(string s1, string s2) {
    int n = s1.size();
    int m = s2.size();
    vector<int> prev(m + 1, 0), cur(m + 1, 0);

    for (int ind1 = 1; ind1 <= n; ind1++) {
        for (int ind2 = 1; ind2 <= m; ind2++) {
            if (s1[ind1 - 1] == s2[ind2 - 1])
                cur[ind2] = 1 + prev[ind2 - 1];
            else
                cur[ind2] = max(prev[ind2], cur[ind2 - 1]);
        }
        prev = cur;
    }
    return prev[m];
}

int longestPalindromeSubsequence(string s) {
    string t = s;
    reverse(s.begin(), s.end());
    return lcs(s, t);
}

int main() {
    string s = "bbabcbcab";
    cout << "The Length of Longest Palindromic Substring is "
         << longestPalindromeSubsequence(s);
}

Looking to excel in your interview within 2 months? Engage in the Blind 75 challenge to gain practical experience with commonly asked questions and essential topics.

Wrapping Up

In this article, we’ve demystified the process of finding the longest palindromic substring using dynamic programming. By employing the concept of the Longest Common Subsequence in an innovative way, we can efficiently solve this coding challenge. The provided C++ code example showcases a clear implementation of the solution, allowing you to better understand the approach and its mechanics. With this knowledge in hand, you’re now better equipped to tackle similar challenges and enhance your problem-solving skills. Happy coding!

Reference

• Problem Link