How to use DP in this problem?

Hello. Could somebody tell me a right DP approach to this problem. I couldn't figure out the solution better than O(|S|*M). |S| - length of the string.

Re: How to use DP in this problem?

Easy problem. Let dp[i] - answer for string S1..Si. Then dp[i]=min(dp[i],dp[i-n]+1). (Maximum possible N-characters message).

If last_idx - index of last "bad" character, then dp[i]=min(dp[i],dp[max(last,i-m)]+1).

If current character is "bad" - update last_idx. It's O(|S|) solution.

Re: How to use DP in this problem?

A pure greedy problem.

You don't need to use any array, the algorithm is very simple:

For each characters, just check if you can add it to the current message, if not you will create a new message and then add it to this message.

Re: How to use DP in this problem?

What is the BAD character in string???