### 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].