AGC-005-A STring

■■■問題■■■

文字列Xが与えられます。Xの長さは偶数であり、半分はS、もう半分はTからなります。

高橋君はSTという文字列が苦手です。なので以下の操作を(10の10000乗)回行うことにしました。
●Xの(連続な)部分文字列でSTとなるもののうち、最も左側にあるものを取り除く。
  存在しないならば何もしない。

最終的にXは何文字になるかを求めてください。

■■■入力■■■

X

●2 <= |X| <= 20万
●Xの長さは偶数
●Xを構成する文字のうち半分はSであり、もう半分はTである

■■■出力■■■

1行に問題の答えを出力する。

C#のソース

using System;
using System.Collections.Generic;

class Program
{
    static string InputPattern = "InputX";

    static List<string> GetInputList()
    {
        var WillReturn = new List<string>();

        if (InputPattern == "Input1") {
            WillReturn.Add("TSTTSS");
            //4
            //1回目の操作ではTSTTSSの2,3文字目がSTなので取り除きます。
            //XはTTSSになり、もうSTはないため残り (10の10000乗)-1回は何もしません。
            //よって答えは4となります。
        }
        else if (InputPattern == "Input2") {
            WillReturn.Add("SSTTST");
            //0
            //SSTTST ⇒ STST ⇒ ST ⇒ 空文字列 となり、
            //最終的に空文字列になります。
        }
        else if (InputPattern == "Input3") {
            WillReturn.Add("TSSTTTSS");
            //4
            //TSSTTTSS ⇒ TSTTSS ⇒ TTSS となります
        }
        else {
            string wkStr;
            while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
        }
        return WillReturn;
    }

    static void Main()
    {
        List<string> InputList = GetInputList();
        string X = InputList[0];

        int SCnt = 0;
        int RemoveCnt = 0;
        foreach (char EachChar in X) {
            if (EachChar == 'S') SCnt++;
            if (EachChar == 'T' && SCnt > 0) {
                RemoveCnt++;
                SCnt--;
            }
        }
        Console.WriteLine(X.Length - RemoveCnt * 2);
    }
}

解説

文字列を順に見ていって、
対応するTがあるSと、
対応するTがないSで、処理を分岐させてます。