#include "hiccup.h"
#include <bits/stdc++.h>
using namespace std;
int N;
string S;
vector <int> hv, cv, ov;
bool works (int K)
{
hv.clear();
cv.clear();
ov.clear();
//cout << S << " " << K << "\n";
int nq = 0;
bool popk = false;
for (int i = 0; i < N; i++)
{
//cout << i << endl;
if (S[i] == 'H')
{
hv.push_back(nq++);
popk = false;
}
else if (S[i] == 'C')
{
cv.push_back(nq++);
popk = false;
}
else
{
if (popk) continue;
ov.push_back(nq++);
}
if (hv.size() > 0 && cv.size() > 0)
{
int h = hv.back(), c = cv.back();
//cout << h << " " << c << " " << K << " " << nq << endl;
if (c == h + 1 && c + K < nq)
{
while (ov.size() > 0 && ov.back() > h)
ov.pop_back();
hv.pop_back();
cv.pop_back();
popk = true;
if (hv.size() > 0 && cv.size() > 0 && cv.back() == hv.back() + 1)
popk = false;
nq = h;
}
}
}
return (hv.size() + cv.size() + ov.size()) == 0;
}
int HicCup(string NOTS) {
S = NOTS;
N = S.length();
if (!works(0))
return -1;
int lo = 0, hi = N;
while (lo < hi)
{
int mid = (lo + hi + 1) / 2;
if (works (mid))
lo = mid;
else
hi = mid - 1;
}
return lo;
}
