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.