Leveraging ChatGPT - GenAI as a Microsoft Data Expert

Speaker

Prerita Agarwal

Data Specialist @

23 Jul, 2024 @ 01:30 PM

Introduction

A palindrome sequence of characters reads the same in both forward and reverse directions. For example, â€śanna.â€ť On both backward and forward reading, itâ€™s â€śanna.â€ť A substring is a contiguous part of a string. Letâ€™s discuss a problem based on these two terms.

Problem Statement

Given a string s, find the length of the longest palindromic substring of the string and also find the number of palindromic substrings of that length.

For example,

Input s = â€śbabadâ€ť

Output 3 1

Explanation: The given string is â€śbabadâ€ť. The substring â€śbabâ€ť is a palindrome, and itâ€™s also the only palindromic substring of this maximum length. So the answer is 3 (maximum length of palindromic substring) and 1 (the number of maximum length palindromic substrings).

Connect with our expert counsellors to understand how to hack your way to success

User rating 4.7/5

1:1 doubt support

95% placement record

Akash Pal

Senior Software Engineer

326% Hike After Job Bootcamp

Himanshu Gusain

Programmer Analyst

32 LPA After Job Bootcamp

After Job Bootcamp

Approach 1: Brute force

The brute force approach to solve this problem is to find all the substrings and, for each substring, check if itâ€™s a palindrome or not. If yes, then check if itâ€™s by far the maximum length palindrome substring or not. Update the maximum length. Once we have found the maximum length, find all the palindromic substrings of this length and increase the count by 1 each time such string is found.

C++ implementation

#include <bits/stdc++.h>
using namespace std;
bool isPalindrome(string temp){
int n = temp.length();
for (int i = 0; i < n/ 2; i++) {
/* if the charcters at index i and n-i-1 are not equal, return false*/
if (temp[i] != temp[n - i - 1]) {
return false;
}
}
/* Else return true*/
return true;
}
int main()
{
string s;
cin>>s;
int mxlength = 0;
/* Variable for storing the maximum length of palindromic substring */
int n = s.length();
/* Traverse all the substrings*/
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
string temp = s.substr(i,j-i+1);
if(isPalindrome(temp)){
/* if the current substring is a palindrome: update the value of maximum length */
int len = j-i+1;
mxlength = max(mxlength,len);
}
}
}
/* variable the stores the number of palindrome substrings of length mxlength*/
int cnt=0;
/* For all the substrings of length mxlength, check how many of them are palindromic. cnt is equal to that number only */
for(int i=0;i<=n-mxlength;i++){
string temp = s.substr(i,mxlength);
if(isPalindrome(temp)){
cnt++;
}
}
cout<<mxlength<<" "<<cnt<<endl;
return 0;
}

Input

cabaabad

Output

6 1

Complexities

Time complexity

O(n^3), where n is the length of the given string

Reason: To go through all the substrings one by one takes O(n^3) time.

In this approach, we try to move around an index on both left and right sides and check if the characters on the left and right sides are equal.

The point to take care of is that, here, weâ€™re considering the current index element as the mid of the palindromic string. But, there can be even length palindromic substrings also. In that case, there is no mid character of the palindromic substring. So, in this case, we will assume a space as a mid-character and check if the characters on the left and right of that space are equal or not.

Letâ€™s understand with an example:

Suppose the string is: â€ścabaabadâ€ť.

Therefore, it is also important to check for even length strings.

Now, letâ€™s discuss how exactly do we check?

For even length substrings: We keep a variable as len, which stores the length till which we can extend in both sides of the character weâ€™re taking as the middle element. Every time we have the left and right character equal (s[i-len]==s[i+1+len]), the new length of the current palindromic substring will be 2*len+2, and we increase the value of len by 1.

For odd length substrings: We keep a variable as len, which stores the length until which we can extend in both sides of the character weâ€™re taking as the middle element. Every time we have the left and right character equal (s[i-len]==s[i+len]), the new length of the current palindromic substring will be 2*len+1, and we increase the value of len by 1.

Once weâ€™ve found the length of the longest palindromic substring, we can look up all the substrings of that length and see how many of them are palindromic. That count will be the second number in the output.

C++ implementation

#include <bits/stdc++.h>
using namespace std;
bool isPalindrome(string temp){
int n = temp.length();
for (int i = 0; i < n/ 2; i++) {
/* if the charcters at index i and n-i-1 are not equal, return false*/
if (temp[i] != temp[n - i - 1]) {
return false;
}
}
/* Else return true*/
return true;
}
/* This is the function that return the maximum length of the palindromic substring of this string */
int maxLengthOfPalindromicSubstring(string s) {
int length = 0;
int len = 0;
/* if the size is two or less, check for the case where the size is two and its two characters are the same */
if (s.size() == 2 and s[0] == s[1]) {
return 2;
}
/* if not, only one element is in the longest palindromic substring, so return 1*/
else if (s.size() < 3) {
string c(1, s[0]);
return 1;
}
string temp;
/*The technique is that, we find a Palindrome string which has size of 2 or 3. If it's a palindrome string, we will try to check if we can extend its length to its both side to find if the extended string is also a palindrome */
for (int i = 0; i < s.size() - 1; i++) {
len = 0;
/* This is for the case where the size of the longest string might be an even number. smallest size possible: 2*/
while ((i-len) >= 0 and (i+1+len) < s.size() and s[i-len] == s[i+1+len]) {
if (length < 2*len+2){
length = 2*len+2;
temp = s.substr(i-len, length);
}
len++;
}
len = 0;
/* This is for the case where the size of the longest string might be an odd number. smallest size possible: 3 */
while ((i-len >= 0) and (i+len < s.size()) and s[i-len] == s[i+len]) {
if (length < 2*len+1) {
length = 2*len+1;
temp = s.substr(i-len, length);
}
len++;
}
}
return temp.length();
}
int main()
{
string s;
cin>>s;
int n = s.length();
int mxlength = maxLengthOfPalindromicSubstring(s);
/* variable the stores the number of palindrome substrings of length mxlength*/
int cnt=0;
/* For all the substrings of length mxlength, check how many of them are palindromic. cnt is equal to that number only */
for(int i=0;i<=n-mxlength;i++){
string temp = s.substr(i,mxlength);
if(isPalindrome(temp)){
cnt++;
}
}
cout<<mxlength<<" "<<cnt<<endl;
return 0;
}

Input

cabaabad

Output

6 1

Complexities

Time complexity

O(n^2), where n is the length of the given string

Reason: For each index i, it takes O(n) time in the worst case to find the maximum length till which we can go on both sides. And there are a total of n indices. Therefore, the total time complexity will be O(n^2).

The idea is to store the information of a substring from index i to index j in a dp array. So basically, the value of dp[i][j] will be 1 if the substring from index i to j is a palindrome. Otherwise, it will be 0.

The recurrence relation will be that, for dp[i][j], we will check if s[i]==s[j] and dp[i+1][j-1]==1. Because for the substring from index i to j to be a palindrome, the last two characters should be equal, and also, the substring from i+1 and j-1 should be a palindrome in itself. In this way, we can find the value of all dp[i][j] for all i from 0 to n and all j from 0 to n (where n is the length of the string).

The base case is all dp[i][i] =1 because the substring from index i to i will be a one character substring, and it will be a palindrome for sure. Also, we will have to initially find the value of dp[i][i+1] as a base case since the recurrence relation is not applicable here. So, we will traverse the whole string once, and, for each index i, we will see if s[i]==s[i+1]. If yes, then, dp[i][i+1]=1, otherwise 0.

Using the above method, the maximum length of the palindromic substring is found. Now, let the length be l, then we can find the number of palindromic substring with this length by traversing all i and for each i, checking if dp[i][i+l-]==1. If yes, then increase the count by 1.

C++ implementation

#include <bits/stdc++.h>
using namespace std;
bool isPalindrome(string temp){
int n = temp.length();
for (int i = 0; i < n/ 2; i++) {
/* if the charcters at index i and n-i-1 are not equal, return false*/
if (temp[i] != temp[n - i - 1]) {
return false;
}
}
/* Else return true*/
return true;
}
/* This is the function that return the maximum length of the palindromic substring of this string */
int maxLengthOfPalindromicSubstring(string s) {
int sz = s.size();
// Base Case Length 1
if(sz == 1) return 1;
// Base Case Length 2
if(sz == 2 && s[0] == s[1]) return 2;
if(sz == 2 && s[0] != s[1]){
return 2;
}
int longest = 1;
/* Dp array for storing if the substring from index i to j is a palindrome or not*/
bool dp[1000][1000] = {0,};
/* For all length 2 substrings */
for(int i = 1;i<sz;++i){
if(s[i-1]==s[i]){
dp[i-1][i] = 1;
longest = 2;
}
else{
dp[i-1][i] = 0;
}
}
for(int i = sz-1;i>=0;i--){
for(int j = i+1;j<sz;j++){
if(s[j] == s[i] && dp[i+1][j-1] == 1){
dp[i][j] = 1;
if(longest<(j-i+1)){
longest = j-i+1;
}
}
}
}
return longest;
}
int main()
{
string s;
cin>>s;
int n = s.length();
int mxlength = maxLengthOfPalindromicSubstring(s);
/* variable the stores the number of palindrome substrings of length mxlength*/
int cnt=0;
/* For all the substrings of length mxlength, check how many of them are palindromic. cnt is equal to that number only */
for(int i=0;i<=n-mxlength;i++){
string temp = s.substr(i,mxlength);
if(isPalindrome(temp)){
cnt++;
}
}
cout<<mxlength<<" "<<cnt<<endl;
return 0;
}

Input

cabaabad

Output

6 1

Complexities

Time complexity

O(n^2), where n is the length of the given string

Reason: Calculating the value of all dp[i][j] takes O(n^2) time.

Space complexity

O(n^2), where n is the length of the given string

Reason: Only space taken is by the dp array, and it is O(n^2).

What is dynamic programming? Dynamic programming is a programming technique used to optimize the solution of problems by remembering the solutions to the subproblems that occur repeatedly and again, hence avoiding solving the same subproblem repeatedly.

What is a palindrome? A palindrome sequence of characters reads the same in both forward and reverse directions. For example, â€śanna.â€ť On both backward and forward reading, itâ€™s â€śanna.â€ť

Is a one-length string always a palindrome? Yes, a one-length string is always a palindrome because it reads the same in forwards and backward reading. For example, â€śaâ€ť reads â€śaâ€ť from both front and back both.

What is a substring? A substring is a contiguous part of a string. For example, for string â€śabbbabaâ€ť, the strings â€śabbaâ€ť, â€śbabaâ€ť, and â€śbbbâ€ť are different substrings.

What is a palindromic substring? A substring that reads the same in both forward and reverse directions, i.e., is a palindrome, is called a palindromic substring.

Key Takeaways

In this article, we have discussed the problem of finding all the longest palindromic substrings. Expanding around the center and Dynamic programming are the two methods discussed here. This problem can also be solved using Manacherâ€™s algorithm. You can read about the algorithm here and try to write the code.

Are you planning to ace the interviews of reputed product-based companies like Amazon, Google, Microsoft, and more? Attempt our Online Mock Test Series onCoding Ninjas Studionow!