TopCoder SRM 670 Div1 Easy: Bracket107

解法

1文字取り出して別のところに挿入するとLCSが最大の文字列が生成される。数は大して大きくないので、全探索でいける。

コード

import java.util.HashSet;

public class Bracket107 {

    public int yetanother(String s) {
	int N = s.length();
	HashSet<String> ansSet = new HashSet<>();
	for (int i = 0; i < N; i++) {
	    char c = s.charAt(i);
	    String tmp = s.substring(0, i) + s.substring(i + 1);
	    for (int j = 0; j < N; j++) {
		String lcs = tmp.substring(0, j) + c + tmp.substring(j);
		if (isOK(lcs)) {
		    ansSet.add(lcs);
		}
	    }
	}
	ansSet.remove(s);
	return ansSet.size();
    }

    private boolean isOK(String string) {
	int c = 0;
	for (int i = 0; i < string.length(); i++) {
	    if (string.charAt(i) == '(') {
		c++;
	    } else {
		c--;
	    }
	    if (c < 0) {
		return false;
	    }
	}
	return true;
    }

}