西側から「自分より西にいるのに西を向いている人の数」を数える。 同時に、東側から「自分より東にいるのに東を向いている人の数」も数える。 最後に、「自分より西にいるのに西を向いている人の数」と「自分より東にいるのに東を向いている人の数」の最小値を計算すれば OK。 計算量は O(2N) かな。
using System; namespace ABC098C { class Program { static void Main(string[] args) { var N = int.Parse(Console.ReadLine()); var S = Console.ReadLine(); var W = new int[N]; var E = new int[N]; var wCount = 0; var eCount = 0; for (var i = 0; i < N; i++) { W[i] = wCount; if (S[i] == 'W') { wCount++; } var j = N - i - 1; E[j] = eCount; if (S[j] == 'E') { eCount++; } } var min = int.MaxValue; for (var i = 0; i < N; i++) { min = Math.Min(min, W[i] + E[i]); } Console.WriteLine(min); } } }