Find Valid Passwords

Problem Statement

Find Valid Passwords Problem Description An engineer is designing a system and needs to create valid passwords. For this purpose, the passwords must follow specific rules based on concatenation and character additions. The engineer proposes rules to be evaluated to ensure it is valid or invalid. The rules are as follows: Password Validation Rules An empty password is always valid. If a valid password A exists, adding the same character 'c' to both the beginning and end of A creates a new valid password 'cAc' . For example, if A = "" (empty string) is valid, adding 'b' gives "bb" which is also valid. If two valid passwords A and B are valid, their concatenations 'AB' and 'BA' are also valid. For example, if "aa" and "bb" are valid, then "aabb" and "bbaa" are valid. The engineer proposed N passwords, each password consisting of lowercase English letters. For each proposed i -th password, determine if the password is valid or invalid. The validity of the i -th password is denoted by 1 in