Search for invalid characters

Instead of checking that we only have valid letters in the
search string we do it the other way around.
By searching for invalid letters we can present the invalid
letters for the user in the error message.