Assume we would like to break a password by trying all possible passwords (brute-force). We are given some clues: 1) The password can be up to 20 characters long.

2) The password contains only numerical characters (from 0 to 9)

3) When we write down the password with letters, there can be no substring starting from index 0, in which the number of vowels is more than the number of consonants. For example; we would like to try the password, 1-3. This cannot be the correct password since 1-3 is written down as "onethree", and the substring "one" contains 2 vowels and 1 consonant which violates the clue #3. This means that the correct password cannot start with "1". Thus, we do not even need to try the number sequence that starts with "1", (e.g., 1-3-2-2-2-2-2-4-5-6) because the sequence fails at the first number. So, we can call "1" an illegal-prefix, since no matter what we add after "1", the sequence will fail. Another example of illegal-prefixes can be "5-2-4-1-8" since it is written down as "fivetwofouroneeight" and the substring "fivetwofouroneei" contains more vowels than consonants.

a) What is the asymptotic complexity of such a problem, when the number of characters that can be used in the password in n and the password can be up to m characters long?

Assume that we start trying all possible password in increasing order (from 0 to 9999..99) and when we encounter a candidate password that violates clue #3 we mark it as illegal-prefix and store it to make sure we will not try consequently generated passwords that contain an illegal-prefix. b) What can be a good data structure that holds discovered illegal prefixes. Explain why? Give another data structure that performs worse than your data structure. Explain why? c) What is the asymptotic complexity of adding/inserting/merging etc. a newly discovered illegal-prefix to your data structure? d) What is the asymptotic complexity of searching a previously discovered illegal-prefix in your data structure?