Password Validation

Time limit1sMemory limit128 MB

Summary
Decide whether each password meets length, character mix, repeat, palindrome, and forbidden subsequence rules.
Level

Medium4 of 10

Topics
Implementation, String, Two pointers
Solved
No attempts yet

Problem

A company needs a password checker for its online system. When a new user submits a password, your program decides whether it is a good password. A good password satisfies every rule below.

  • The length is between 9 and 20 characters, inclusive. A length of exactly 9 or exactly 20 is allowed.
  • It contains at least 2 lowercase letters.
  • It contains at least 2 uppercase letters.
  • It contains at least 1 digit.
  • It contains at least 2 non-alphanumeric characters. The only non-alphanumeric characters that appear in a password are : ! @ # $ % ^ & * . , ; / ?.
  • No character occurs three times in a row. Case matters, so aAa is allowed and aaa is not.
  • Drop every non-alphanumeric character and ignore case. The string of letters and digits that remains is not a palindrome. For example, &Ra^#r leaves rar, which is a palindrome.
  • Drop every non-alphanumeric character and ignore case. In the string that remains, no subsequence read forward and no subsequence read backward equals one of the words below. A subsequence keeps the original order, but its characters do not have to be adjacent. For example, pKassWordL and KdRrowSmsap are both invalid passwords.
    • password
    • virginia
    • cavalier
    • code

Input

The first line contains an integer N, the number of test cases. Each of the next N lines contains one password to check. A password contains no spaces.

Output

Print one line per test case: Valid Password if the password satisfies every rule above, and Invalid Password if it breaks at least one of them.

Examples1

  1. Example 1

    Input
    3
SPring2011!!
pKassW&ordL*
123^45ABcde.
    Expected output
    Valid Password
Invalid Password
Valid Password