[Java]年俸1000万の会社の試験問題(JavaではなくPHPで実装)

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

速度的な問題もあるのでできれば, 重複を省く処理を入れたくはないのだが, 入れざるを得ない・・・

<?php 
/**
 * 任意の重複しないA, C, G, Tから成る長さn-3から成る文字列に対して, その文字列の任意の箇所に文字列"AAG"を埋め込んで
 * 得られる文字列は, 題意を満たす. ただし, この方法で求めた文字列には重複が存在する. そこで重複を全て省いた結果が求める
 * 文字列集合である.
 */

function padZero($string, $length) {
    if (strlen($string) < $length) {
        return padZero("0".$string, $length);
    }
    return $string;
}

function insertString($base_string, $insert_string, $position) {
    $length = strlen($insert_string);
    $value1 = substr($base_string, 0, $position);
    $value2 = $insert_string;
    $value3 = substr($base_string, $position, strlen($base_string));
    return $value1.$value2.$value3;

}

function solve($n) {
    $key = "002";
    $value;
    $hash = array();
    $answer = array();
    for ($i = 0; $i < PHP_INT_MAX; $i++) {
        $value = base_convert($i, 10, 4);
        if (strlen($value) <= $n - 3) {
            $hash[] = padZero($value, $n - 3);
        } else {
            break;
        }
    }

    for ($i = 0, $size = count($hash); $i < $size; $i++) {
        for ($j = 0, $length = strlen($hash[$i]) + 1; $j < $length; $j++) {
            $value = insertString($hash[$i], $key, $j);
            $answer[$value] = true;
        }
    }
    $hash = null;

    $count = 0;
    $replace_from = array("0", "1", "2", "3");
    $replace_to = array("A", "C", "G", "T");
    foreach($answer as $key => $value) {
        echo str_replace($replace_from, $replace_to, $key)."\n";
        $count ++;
    }
    echo "Count: $count\n";
}

// 実行
solve(10);
?>