Given a String s
, return the number of palindromic subsequences of length 5.
Test case 1:
input : "abcdba"
Output : 2
"abcba" and "abdba"
Test case 2:
input : "aabccba"
Output : 4
"abcba" , "abcba" , "abcba" , "abcba"
Max length of String: 700
My TLE Approach: O(2^n)
https://www.online-java.com/5YegWkAVad
Any inputs are highly appreciated...
CodePudding user response:
- Whenever 2 characters match, we only have to find how many palindromes of length 3 are possible in between these 2 characters.
For example:
a bcbc a
^ ^
|_ _ _ |
In the above example, you can find 2 palindromes of length 3
which is bcb
and cbc
. Hence, we can make palindromic sequence of length 5
as abcba
or acbca
. Hence, the answer is 2
.
Computing how many palindromes of length 3 are possible for every substring can be time consuming if we don't cache the results when we do it the first time. So, cache those results and reuse them for queries generated by other 2 character matches. (
a.k.a dynamic programming
)This way, the solution becomes quadratic
O(n^2)
time wheren
is length of the string.
Snippet:
private static long solve(String s){
long ans = 0;
int len = s.length();
long[][] dp = new long[len][len];
/* compute how many palindromes of length 3 are possible for every 2 characters match */
for(int i = len - 2;i >= 0; --i){
for(int j = i 2; j < len; j){
dp[i][j] = dp[i][j-1] (dp[i 1][j] == dp[i 1][j-1] ? 0 : dp[i 1][j] - dp[i 1][j - 1]);
if(s.charAt(i) == s.charAt(j)){
dp[i][j] = j - i - 1;
}
}
}
/* re-use the above data to calculate for palindromes of length 5*/
for(int i = 0; i < len; i){
for(int j = i 4; j < len; j){
if(s.charAt(i) == s.charAt(j)){
ans = dp[i 1][j - 1];
}
}
}
//for(int i=0;i<len; i) System.out.println(Arrays.toString(dp[i]));
return ans;
}
Update:
dp[i][j] = dp[i][j-1] (dp[i 1][j] == dp[i 1][j-1] ? 0 : dp[i 1][j] - dp[i 1][j - 1]);
The above line basically mean this,
- For any substring, say
bcbcb
, with matching first and lastb
, the total 3 length palindromes can be addition of- The total count possible for
bcbc
. - The total count possible for
cbcb
. - The total count possible for
bcbcb
(which is(j - i - 1)
in theif
condition).
- The total count possible for
dp[i][j]
For the current substring at hand.dp[i][j-1]
- Adding the previous substring counts of length 3. In this example,bcbc
.dp[i 1][j]
, Adding the substring ending at current index excluding the first character. (Here,cbcb
).dp[i 1][j] == dp[i 1][j-1] ? 0 : dp[i 1][j] - dp[i 1][j - 1]
This is to basically avoid duplicate counting for internal substrings and only adding them if there is a difference in the counts.