TopCoder SRM 663 Div1 Easy: ABBADiv1

解法

targetの文字列のうち、initialあるいはinitialの反転部分を見つけ、その前後のBの数が条件にあっているかどうか確かめる。1回以上Bによる反転操作がある場合、絶対に先頭にAは来ない（これで落ちた）。

コード

public class ABBADiv1 {

	public String canObtain(String initial, String target) {
		StringBuffer sb = new StringBuffer(initial);
		String reverse = sb.reverse().toString();
		if (check(initial, target, 0)) {
			return "Possible";
		}
		if (check(reverse, target, 1)) {
			return "Possible";
		}
		return "Impossible";
	}

	private boolean check(String initial, String target, int reverse) {
		search: for (int start = 0; start <= target.length() - initial.length(); start++) {
			for (int i = 0; i < initial.length(); i++) {
				if (target.charAt(start + i) != initial.charAt(i)) {
					continue search;
				}
			}
			// 見つけた文字列と、その位置
			int end = start + initial.length();
			String prefix = target.substring(0, start);
			if (start == 0) {
				prefix = "";
			}
			String suffix = target.substring(end, target.length());
			if (end == target.length()) {
				suffix = "";
			}
			int bCnt = 0;
			for (int i = 0; i < prefix.length(); i++) {
				if (prefix.charAt(i) == 'B') {
					bCnt++;
				}
			}
			for (int i = 0; i < suffix.length(); i++) {
				if (suffix.charAt(i) == 'B') {
					bCnt--;
				}
			}
			if (bCnt == reverse) {
				if (prefix.length() == 0 || prefix.charAt(0) == 'B') {
					return true;
				}
			}

		}
		return false;
	}
}