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.

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.

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.

What is the BAD character in string???