Password Validation Rules

Problem Statement

Password Validation Rules An engineer is designing a system and needs to know which proposed passwords the system will accept. Every password is a string of lowercase English letters, and a password is valid exactly when it can be built from nothing by the following three rules. The empty password is valid. If A is a valid password and X is a letter, then XAX is valid. For example, from the valid password aa and the letter b the rule builds baab . If A and B are valid passwords, then AB and BA are valid. For example, from the valid passwords aa and bb the rule builds aabb and bbaa . Given n proposed passwords, decide for each one whether it is valid. The task is exposed as a function findValidPasswords that takes the array of passwords and returns an array of integers, 1 for a valid password and 0 for an invalid one. Input Format The first line contains an integer n , the number of proposed passwords. Each of the next n lines contains one password, a non-empty string of lowercase Engli