|
|
back to boardDiscussion of Problem 1427. SMSShow all messages Hide all messagesHello. 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??? |
|
|
