Put them in a set(), then iterate over its members and report any that contain b and are still in the set after the string replacement. O(n), which can't be beaten.
Edit: If you're downvoting, could you post a comment saying why?
That is, if Ws is the set of 5-letter words we want the set Rs = {w: w ∈ Ws, w.replace(b,o) ∈ Ws}. You can see that that's an O(n²) operation (each ∈ is an iteration over Ws).
jayd16 proposed omitting every word that has a b in it from the "search space". I take this to mean, in practice, that we start by initialising a set Ss = {w: w ∈ Ws, b ∉ w}. Then Rs = {w: w ∈ Ws, w.replace(b,o) ∈ Ss} and the time complexity is O(|Ws||Ss|) which is again O(n²) in the worst case (where Ws = Ss). Note also that some words in Ws may have more than one b and since we are only replacing "a b" (i.e. one b) we may remove valid words this way.
In any case, I don't see an obvious way to do this in O(n). Maybe I'm not thinking straight though, it's way past bed time.
In any case, even if it was O(n²) that's a polynomial time complexity and I don't see why BDDs are needed.
More, an O(n) algorithm can be more "efficient" than an O(lg(n)) one, for some values of n. (Or just in another facet. Maybe you actually do care about space.)
The claim wasn't how to do it fast, per se. It was how to do it efficiently. And comparing two algorithms of the same order can have a wide difference in the answer.
So you fill the set with in O(1*N), again loop through the (original?) list assuming its O(N) to do so searching the set for replacements?
So at least a few passes through every element.
You could actually reduce this by excluding elements as you insert. You don't need to fill your search space with with anything that has a "b" for example, eliminating inserts.
I'm not sure that works. Suppose "abab" and "abao" are words. Note the problem spec says "after replacing a b with an o", i.e. after replacing _one_ b in a word with an o. If you exclude all words with a "b" and replace one b with an o in "abab" you will get "abao" which you have excluded, so you will think it's not a word. I think at best you can ignore only words with a single b.
However you can skip words that started with no Bs as clearly still being words without a search and you can remove search words with no Os.
You’re right to think this is impossible though. Grover’s algorithm was one of the first examples of something that clearly could not ever exist classically.