Movatterモバイル変換

[0]ホーム
URL:

Skip to content

Navigation Menu

Sign in
Appearance settings

Search code, repositories, users, issues, pull requests...

Provide feedback

We read every piece of feedback, and take your input very seriously.

Saved searches

Use saved searches to filter your results more quickly

 Sign up
Appearance settings

Commit70798be

Browse files
authored
Merge pull requestneetcode-gh#1993 from Maunish-dave/2002-maximum-product-of-the-length-of-two-palindromic-subsequences
Create 2002-maximum-product-of-the-length-of-two-palindromic-subsequences.cpp
2 parents18e8a3f +4f1ef7d commit70798be

File tree

1 file changed

+81
-0
lines changed

1 file changed

+81
-0
lines changed
Lines changed: 81 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,81 @@
1+
/*
2+
Approach:
3+
Need to create all the disjoin subsequence and check if they are palindrome.
4+
keep track of maximum product
5+
6+
Time complexity : O(N*N^3)
7+
Space complexity: O(N)
8+
9+
N is length of the string
10+
*/
11+
12+
13+
classSolution {
14+
public:
15+
16+
int answer = INT_MIN;
17+
18+
// function to check if the string is a palindrome
19+
boolisPalindrome(string &s){
20+
int start =0;
21+
int end = s.length() -1;
22+
23+
while(start<end){
24+
if(s[start]!=s[end]){
25+
returnfalse;
26+
}
27+
start++;
28+
end--;
29+
}
30+
31+
returntrue;
32+
}
33+
34+
// function to generate all the disjoint subsequence
35+
voidgenerateAll(int idx, string &s1, string &s2, string& s){
36+
37+
if(idx >= s.length())
38+
{
39+
if(isPalindrome(s1)&&isPalindrome(s2)){
40+
int l = s1.length()*s2.length();
41+
answer =max(answer,l);
42+
}
43+
return;
44+
}
45+
46+
char c = s[idx];
47+
48+
/*
49+
we have three options
50+
1. Add the char to the first string
51+
2. Add the char to the second string
52+
3. Add the char to none of the string
53+
*/
54+
55+
// add the character in the first string
56+
s1.push_back(c);
57+
generateAll(idx+1,s1,s2,s);
58+
s1.pop_back();
59+
60+
// add the character in the second string
61+
s2.push_back(c);
62+
generateAll(idx+1,s1,s2,s);
63+
s2.pop_back();
64+
65+
// add character in no string
66+
generateAll(idx+1,s1,s2,s);
67+
}
68+
69+
intmaxProduct(string s) {
70+
71+
string s1 ="";
72+
string s2 ="";
73+
int idx =0;
74+
75+
generateAll(idx,s1,s2,s);
76+
77+
return answer;
78+
}
79+
80+
81+
};

0 commit comments

Comments
 (0)
[8]ページ先頭
©2009-2025 Movatter.jp