You can't have more productive threads than you have processors. (I'm ignoring I/O for now.) Lets suppose maxThreads is the total maximum number of threads you want to have. This is a soft limit. It may get exceeded temporarily, but the excess will correct itself.
Have a queue of unchecked strings, initially empty. Start one StringChecker thread.
Every time a StringChecker sees the queue empty, it starts a new StringGenerator thread. If the total number of threads now exceed maxThreads and this is not the only StringChecker thread, it stops. Otherwise, it pulls a string from the queue and checks it.
Every time a StringGenerator has a string ready to be checked but finds the queue is full, it starts a new StringChecker thread. After waiting for the queue to unblock and let it put its string into the queue, if the total number of threads now exceeds maxThreads and it is not the last StringGenerator, it stops.
Better Answer
I was playing out in my mind how this system and the one described by @rwong would behave, and realized we're going at this all wrong. How long it takes to generate a string versus how long it takes to check one is irrelevant. When the system reaches steady state, it will be checking strings at exactly the same rate it generates them. stringsGenerated = stringsChecked + stringsInQueue + stringsBeingChecked, and the last two terms are both small and bounded.
That means you may as well start as many threads as you deem useful, and have each thread:
loop
generate a string
check it
end loop
I see that @Doval had the same idea, so I +1ed his comment.