Thank you.

Good idea, relying on the manageable size of the acceptable strings.
Using a HashSet rather than an ArrayList would speed that up: in a lookup, ArrayLists loop over all their elements, while HashSets, thanks to hashing, don't need to.

good structure, but the list of acceptable eyes, noses and mouths is created again and again every time a validation method is called.
Creating and storing them once for all in a constant will improve the performances.

Also, if you plan to use the "contains" method I would advise to consider HashSets which answers that question faster than ArrayLists. But in this case it doesn't matter much given the size of the collection is 2 in all the cases.

O(n) time, probably the best accepting O(d) space, where d are the distinguished integers in the array

not to mention many other solutions are O(n) but this is (n^2)...