[Java]年俸1000万の会社の試験問題[速度重視]

4種類のアルファベット "A,C,G,T" から成るn文字の文字列のうち、
"AAG"という並びが含まれる文字列を全て列挙するプログラムを書きなさい。
ただし、nは3以上の整数とし、文字列内に同じアルファベットが出現しても構わないものとし、
出力順序は問わないものとします。
http://alpha.cgios.net/alpha/cgios

初投稿。しょぼい知識で高速化を図ってみました。もっといい方法あれば教えて下さい。

ACGTLogic.java

public class ACGTLogic {
	static final String[] CHARS = { "A", "C", "G", "T" };
	static final String REQUIRE_STR = "AAG";

	Map<Integer, List<String>> cache;

	public List<String> getList(int n) {
		if (n == REQUIRE_STR.length()) {
			List<String> list = new ArrayList<>();
			list.add(REQUIRE_STR);
			return list;
		}

		int reqNum = n - REQUIRE_STR.length();

		cache = new HashMap<>();
		List<String> pre, suf;
		Set<String> setList = new HashSet<>();
		createCache(reqNum);
		for (int i = 0; i <= reqNum; i++) {
			pre = cache.get(i);
			suf = cache.get(reqNum - i);

			for (int preIdx = 0; preIdx < pre.size(); preIdx++) {
				String preStr = pre.get(preIdx);
				for (int sufIdx = 0; sufIdx < suf.size(); sufIdx++) {
					setList.add(new StringBuilder().append(preStr).append(REQUIRE_STR).append(suf.get(sufIdx))
							.toString());
				}
			}
		}
		List<String> res = new ArrayList<>(setList);
		Collections.sort(res);
		return res;
	}

	private void createCache(int reqNum) {
		List<String> list = new ArrayList<>();
		list.add("");
		cache.put(0, list);
		for (int rep = 0; rep < reqNum; rep++) {
			List<String> tmp = new ArrayList<>();
			for (int i = 0; i < list.size(); i++) {
				for (int j = 0; j < CHARS.length; j++) {
					tmp.add(new StringBuilder().append(list.get(i)).append((CHARS[j])).toString());
				}
			}
			cache.put(rep + 1, tmp);
			list = tmp;
		}
	}
}