PROBLEM LINK:
Author: Abhinav Jha
Tester: Ankit Raj Gupta
Editorialist: Abhinav Jha
DIFFICULTY: Easy
PREREQUISITES: Dynamic Programming
PROBLEM: Find the longest sub-sequence consisting of characters I, E and M in order in a string.
EXPLANATION:
This is a problem on dynamic programming and can be solved by constructing a table of size 3x(len(string) + 1).
The 3 rows of the table correspond to the longest subsequence in the string that end with letters ‘I’, ‘E’ and ‘M’ respectively.
This means that for any integer i <= len(string) :
(a) dp[0][i] means the longest subsequence upto position i-1 in string such that it ends with ‘I’
(b) dp[1][i] means the longest subsequence upto position i-1 in string such that it ends with ‘E’
© dp[2][i] means the longest subsequence upto position i-1 in string such that it ends with ‘M’
One thing to be taken care is that as long as I has not been encountered in the string, even if E is encounter than it is invalid and has to be discarded.
Similarly as as long as I and E have not been encountered in the string, even if M is encounter than it is invalid and has to be discarded.
Finally the answer is the longest subsequence upto position n-1 in string (0-indexed) such that it ends with ‘M’. So answer in our table is dp[2][n].