\(S\) の \(i\) 文字目から \(i+K-1\) 文字目までがすべて丈夫であるときに左から \(i,i+1,\ldots,i+K\) 番目にある歯を使ってイチゴを食べ、\(S\) の \(i\) 文字目から \(i+K-1\) 文字目までをすべて X に変更するという操作を \(i=1,2,\ldots,N-K+1\) の順番で行うことで最大数のイチゴを食べることができます。

実際にこの方法で食べることでイチゴを最大の個数食べられることは、ある連続した丈夫な歯を使って最大の個数のイチゴを食べるには左から順に \(K\) 本ずつ歯を使うことでできることより示せます。

実装する際には、文字列に対する操作が求められます。各言語における文字列の機能などを知っておくことで簡単に、短く実装できる場合があります。例えばある部分文字列を取得する時はC++では substr を用いることでよりシンプルに実装出来ます。

実装例(C++)

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n, k;
    cin >> n >> k;
    string s;
    cin >> s;
    int ans = 0;
    string t = string(k, 'O');
    for (int i = 0; i < n - k + 1; ++i) {
        if (s.substr(i, k) == t) {
            ans++;
            for (int j = i; j < i + k; j++) {
                s[j] = 'X';
            }
        }
    }
    cout << ans << endl;
}

実装例(Python3)

n, k = map(int, input().split())
s = list(input())
ans = 0
t = 'O' * k

for i in range(n - k + 1):
    if s[i:i + k] == list(t):
        ans += 1
        for j in range(i, i + k):
            s[j] = 'X'

print(ans)