Please Provide the Algorithm as well as Code for the count of the Palindromic Subsequence in the user EnteredString in Java Prrograming Language.
Required:
Please provide the Algorithm as well as Code for the count of the Palindromic Subsequence in the user
Entered String in Java Programming Language.
Approach:
Take the String from the user using the scanner class object and then find the count of the Palindromic Subsequences of that String
Algorithm:
Base Cases:
- if the string length is 1: then only 1 Palindromic Subsequence is Present.
- if the string length is 2 then we have to check whether the last character is equal then its count will be 3 else it will be 2.
Count of subsequence(ABCD)
C(c1 + m + c2) : __C(BC)__ , __C(BC)D, AC(BC)__, AC(BC)D
ABCD = c1mc2 ---> Representation
from the above subsequence: we can say that if the first and last of the subsequence character is equal then count_of_subsequence(str) = count_of_subsequence(c1m) + count_of_subsequence(mc2) + 1;
if unequal then count_of_subsequence(str) =count_of_subsequence(c1m) +count_of_subsequence(mc2) - count_of_subsequence(m);
Coding:
Just Iterate over the 2D array along the gap and find the total number of palindromic subsequences which came at the top right corner and print the result on the console.
for further help, please see the code below with the output.
Step by step
Solved in 4 steps with 3 images
