Senza andare a "scomodare" le espressioni regolari (tra l'altro per cercare una stringa qualunque con le regex si dovrebbe "quotarla"), io farei:

codice:
public static boolean stringInString (String str, String search, int minCount)
{
    int count = 0, idx = 0, len = search.length ();

    while ((idx = str.indexOf (search, idx)) != -1)
    {
        count++;
        idx += len;
    }

    return count >= minCount;
}
Semplice e veloce.