辞書最小の問題

問題概要

入力：N文字の文字列S、長さ０の文字列T
以下の操作を行い、辞書順比較でできるだけ小さい文字列Tを作れ。
・Sの先頭を１文字削除し、Tの末尾に追加
・Sの末尾を１文字削除し、Tの末尾に追加

問題考察

貪欲法を使う。
先頭の文字が小さければ小さいほど、良い。
▶︎先頭から取り得る最も適切な値を選んでゆく。

比較文字列が同じ場合、文字列を片方反転し比較する。

回答コード(C#)

class TradeString
{
	public string Trade(int num, string S){
		int head = 0;
		int end = num - 1;
		string s_head = "";
		string s_end = "";
		string T = "";
		string RevS = "";

		//Reversed String at Same Cost
		for(int i=num-1; i >= 0; i--){
			RevS += S.Substring (i, 1);
		}
		while(head <= end) {
			s_head = S.Substring (head, 1);
			s_end = S.Substring (end, 1);
			int cmp = s_head.CompareTo (s_end);
			if (cmp < 0) { //head < end
				T = T + s_head;
				head++;
			} else if (cmp > 0) { //head > end
				T = T + s_end;
				end--;
			} else {	// head == end
				string s_head1 = S.Substring (head);
				string s_end1 = RevS.Substring (num-end);
				int sCmp = s_head1.CompareTo(s_end1);
				if (sCmp < 0) { //head < end
					T = T + s_head;
					head++;
				} else { // head > end or head == end
					T = T + s_end;
					end--;
				}
			}
			Console.WriteLine ("head:" + head.ToString () + "end:" + end.ToString ());
			Console.WriteLine ("s_head:" + s_head + ",s_end:" + s_end);
		}
		return T;
	}
}