First, we note that there exists an $O(NK)$ dynamic-programming solution. Let $dp[v]$ represent the answer to the problem on the prefix $s[0, 1, \ldots, v - 1]$. Let $c_{ij} = 1$ if the range $s[i, i + 1, \ldots j - 1]$ is at least half Guernseys, and $0$ otherwise. Then, observe that

Observe that if we let $p[i]$ equal the difference between the number of Holsteins and Guernseys in the range $s[0, 1, \ldots i - 1]$, then $c_{ij} = \begin{cases} 1, \text{ if } p[i] \le p[j] \\ 0, \text{ if } p[i] > p[j] \end{cases}$ which allows us to compute $c_{ij}$ in $O(1)$ time by precomputing $p[0], p[1], \ldots p[n]$.

Implemented naively, this solution is $O(NK)$. However, observe that $0 \le c_{ij} \le 1$ for all $i, j$. Thus, notice that

Define here $m = \min_{\max(0, j - K) \le i \le j - 1}(dp[i])$ It therefore suffices to check whether there exists an $i$ such that

1. A multiset storing all the values of $dp[i]$.

2. A map from each value of $dp[i]$ to the multiset of corresponding possible $pre[i]$'s.

Then, to check whether there exists an $i$ satisfying the requirement, it suffices to first compute $m$, and then find the lowest possible value of $p[i]$ among all $i$ with $dp[i] = m$, and check whether that is lower than $p[j]$, which suffices to solve the problem. My code is below:

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

int DP[300001];
int pref[300001];
int main() {
    int N, K; cin >> N >> K;
    string s; cin >> s;
    DP[0] = 0;
    pref[0] = 0;
    for (int i = 0; i < (int) s.size(); i++){
      if (s[i] == 'H'){
        pref[i + 1] = pref[i] + 1;
      }
      else{
        pref[i + 1] = pref[i] - 1;
      }
    }
    //contains all values of dp[i] that are active
    multiset<int> dpvals;
    dpvals.insert(0);
    //contains the values of pre[i] given dp[i]
    multiset<int> elements[300001]; 
    elements[0].insert(0);
    for (int i = 1; i <= N; i++){
      //query
      int mnval = *(dpvals.begin());
      if (*elements[mnval].begin() < pref[i]){
        DP[i] = mnval;
      }
      else{
        DP[i] = mnval + 1;
      }
      dpvals.insert(DP[i]);
      elements[DP[i]].insert(pref[i]);
      //update
      if (i >= K){
        dpvals.erase(dpvals.find(DP[i - K]));
        elements[DP[i - K]].erase(elements[DP[i - K]].find(pref[i - K]));
      }
    }
    cout << DP[N] << endl;
}