LWS - Editorial

PROBLEM LINKS

Practice
Contest

DIFFICULTY

EASY

EXPLANATION

Longest Weird Subsequence: This problem can be solved using dynamic programming. The trick to this problem was to come up with a good dp state. We can make use of the fact that the only allowed characters in the input string S[1…n] are the lowercase Latin letters i.e. ‘a’ – ‘z’. Thus, the distinct number of characters that can appear cannot be greater than 26. Hence we come up with the following dp state: dp[k][c1][c2] = length of the LWS for the substring S[1…k] such that the non-decreasing subsequence ends with c1 and the non-increasing subsequence ends with c2. Once we have decided the state, we can easily come up with the following recurrence: To calculate dp[k][c1][c2] we try to add the lowercase letter S[k] to either non-increasing subsequence or non-decreasing subsequence or we do not add it to any of them. Thus, if c1<=S[k]: dp[k][S[k]][c2] = max(dp[k][S[k]][c2], dp[k-1][c1][c2]+1) and similarly if c2>=S[k] dp[k][c1][S[k]] = max(dp[k][c1][S[k]], dp[k-1][c1][c2]+1) The final answer can be found out by iterating over c1 and c2 and finding the maximum value out of all dp[n][c1][c2]. We can see that we have to calculate 26 * 26 states for every possible length of a substring from 1 to n where n is the length of the string. Thus, the order of the solution is O(2626n).

SETTER’S SOLUTION

Can be found here.

TESTER’S SOLUTION

Can be found here.

1 Like

@harsh93 Can you please explain what you have done in your solution- http://www.codechef.com/viewsolution/1655226

1 Like

I am not able to get the logic. Why are we making a 3d array? Any advice for getting the thinking pattern will be very helpful.

1 Like

What is use of this line dp[k][i][j]=max(dp[k][i][j],dp[k-1][i][j]) in setter’s solution?

1 Like