EDITORIAL - DON (IEMCO16)

PROBLEM LINK:

Contest

Practice

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’
(c) 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].

AUTHOR’S SOLUTION:
Author’s solution can be found here