If \(S_1 \neq S_N\), one operation is enough. Now, let us assume \(S_1=S_N\). If there is an index \(i\) such that \(S_i \neq S_1\) and \(S_{i+1} \neq S_1\), two operations is enough: we can delete \([1,i]\) and then \([i+1,N]\).

Otherwise, the answer is \(-1\), which can be proved inductively.

The complexity of this solution is \(O(N)\).