$S$ が O のみの場合は簡単なので、 I を含んでいるとします。
まず、 $S$ の非連続でもよい最長の部分文字列で、判子となりうるもの $S'$ を取ります。ここで、 $S$ をランレングス圧縮したものを考えると、 $S'$ は同じ文字が連続している部分から(抜き出す場合は) $1$ つずつ抜き出したものとなります。
例えば、 $S=$ IOOOIOOI なら $\{$ I $,1 \}, \{$ O $,3 \}, \{$ I $,1 \}, \{$ O $,2 \}, \{$ I $,1 \}$ とランレングス圧縮でき、全ての部分から $1$ つずつ取り出して得られる IOIOI が $S'$ として最適です。これを判子としたときの必要回数は $N- |S'|$ です。

ここで、長さを $2$ 増やすことを考えます。新しく I と O を使う位置を決める必要があり、これは同じ部分からである必要があります。 $2$ つの文字を使う位置が異なる部分にある場合、その $2$ つの間に既に判子を対応させる文字があるので回数の最適性が失われます。
またこのように長さを $2$ 増やすと必要回数が $1$ 減ることが分かります。

これを基にして、 \(S'\) となるものを取った後、取れるだけ残りの部分から連続した同じ文字 \(2\) 文字分を割り当てていけばよいです。

計算量は \(O(N)\) です。