Shrinking [AtCoder Grand Contest 016 A]

atcoder.jp

実装力が問われる問題だと思います。

長さ N の文字を長さ N-1 の文字に変える際、N の i 文字目と i+1 文字目のどちらかを選びますが、このとき選ぶ文字を「寄せる文字」と呼ぶことにします。

S の長さは最大でも 100 なので、寄せる文字を a～z まで全探索することが可能です。

寄せる文字を選ぶ際には、i 文字目か i+1 文字目に c があれば c を選び、c がなければ i 文字目を選ぶ、というふうにして選んでいき、この c を a から z まで試していけばよいです。

void solve () {

	String s = next();
	int min = MAX_INT;

	for (int i=0; i<26; i++) { //a-z(+97)

		String temp = s;
		int count = 0;
		char c = (char)(i+97);

		//文字列の長さが1になるまで操作する
		while (temp.length() > 1) {

			//文字列が全て同じ文字から構成されているならループを抜ける
			if (allSameChar(temp, c) == true) break;

			StringBuilder sb = new StringBuilder();
			for (int j=0; j<s.length()-count-1; j++) {
				if (temp.charAt(j)==c || temp.charAt(j+1)==c) {
					sb.append(c);
				}
				else sb.append(temp.charAt(j));
			}

			temp = sb.toString(); //文字列を操作後のものに更新する
			count++;

		}

		min = Math.min(min, count); //最小値の更新

	}

	out.println(min);

}


//文字列が全て同じ文字から構成されているかどうかを判定するメソッド
static boolean allSameChar (String s, char c) {
	for (int i=0; i<s.length(); i++) {
		if (s.charAt(i) != c) return false;
	}
	return true;
}