#include <iostream>
#include <string>
#include <vector>
using namespace std;
string longestPalindromicSubstring(const string& s) {
int n = s.length();
if (n == 0) return "";
vector<vector<bool>> dp(n, vector<bool>(n, false));
int start = 0, maxLength = 1;
// All substrings of length 1 are palindromes
for (int i = 0; i < n; ++i) {
dp[i][i] = true;
}
// Check for substrings of length 2
for (int i = 0; i < n - 1; ++i) {
if (s[i] == s[i + 1]) {
dp[i][i + 1] = true;
start = i;
maxLength = 2;
}
}
// Check for substrings of length greater than 2
for (int len = 3; len <= n; ++len) {
for (int i = 0; i < n - len + 1; ++i) {
int j = i + len - 1;
if (s[i] == s[j] && dp[i + 1][j - 1]) {
dp[i][j] = true;
start = i;
maxLength = len;
}
}
}
return s.substr(start, maxLength);
}
int main() {
string s = "babad";
string substring = longestPalindromicSubstring(s);
cout << "Longest Palindromic Substring is: " << substring << endl;
return 0;
}
Finding the Longest Palindromic Substring
Asked 7 months ago
1Comments
40 Views
A palindromic substring is a sequence of characters that reads the same forward as backward. For example, "mom", "lool", "noon", etc. Given a string, the task is to find the longest palindromic substring within it.
Example
For the string "babad", the longest palindromic substring is "bab" or "aba".
Approach
To solve this problem, we need to follow these steps:
- Find all substrings of the given string
- Check which substrings are palindromic
- Return the longest (maximum) palindromic substring
Step-by-step Explanation
isPalindrome() Function
This function checks if a given substring is a palindrome or not.
- It takes a string
sand two indicesstartandendas parameters. - It uses a
whileloop to compare characters from thestartandend, moving towards the center. - If at any point the characters are not equal, the function returns
false. - If the loop completes without finding any mismatch, the function returns
true.
longestPalindromicSubstring() Function
- This function initializes an empty string
ansto store the longest palindromic substring found. - It uses two nested loops to iterate over all possible substrings in the input string
s. - For each substring, it calls the
isPalindromefunction to check if it's a palindrome. - If it is, the substring is compared with the current longest palindromic substring (
ans), and if it's longer, it replaces the currentans. - After both loops complete, the function returns the longest palindromic substring found.
Main Function
In the main function, we've defined a string s = "babad" as an example input. We then call the longestPalindromicSubstring function with this input string, and the result is printed as the output.
#include <iostream>
#include <string>
using namespace std;
// Function to check if a given substring is a palindrome
bool isPalindrome(const string& s, int start, int end) {
while (start < end) {
if (s[start] != s[end]) {
return false;
}
start++, end--;
}
return true;
}
// Function to find the longest palindromic substring
string longestPalindromicSubstring(const string& s) {
string ans = "";
for (int i = 0; i < s.length(); i++) {
for (int j = i; j < s.length(); j++) {
string t = s.substr(i, j - i + 1);
if (isPalindrome(s, i, j) && t.length() > ans.length()) {
ans = t;
}
}
}
return ans;
}
int main() {
string s = "babad";
string substring = longestPalindromicSubstring(s);
cout << "Longest Palindromic Substring is: " << substring << endl;
return 0;
}This is a brute force approach with a time complexity of O(n^3), where n is the length of the input string. While it works correctly, it's inefficient for large input strings. The optimal solution can be obtained using dynamic programming, which has a time complexity of O(n^2). However, the dynamic programming approach is more complex and may be challenging for beginners to understand initially
Try yourself in LEETCODE : https://leetcode.com/problems/longest-palindromic-substring/description/
medium
Share