Looking for good programming challenges?

Use the search below to find our solutions for selected questions!

Password Cracker challenge

Sharing is caring!

Problem statement
There are N users registered on a website CuteKittens.com. Each of them have a unique password represented by pass[1], pass[2], \dots, pass[N]. As this a very lovely site, many people want to access those awesomely cute pics of the kittens. But the adamant admin don’t want this site to be available for general public. So only those people with passwords can access it.

Yu being an awesome hacker finds a loophole in their password verification system. A string which is concatenation of one or more passwords, in any order, is also accepted by the password verification system. Any password can appear 0 or more times in that string. He has access to each of the N passwords, and also have a string loginAttempt, he has to tell whether this string be accepted by the password verification system of the website.

For example, if there are 3 users with password {abra, ka, dabra}, then some of the valid combinations are abra (pass[1]), kaabra (pass[2]+pass[1]), kadabraka (pass[2]+pass[3]+pass[2]), kadabraabra (pass[2]+pass[3]+pass[1]) and so on.

Input Format
First line contains an integer T, the total number of test cases. Then T test cases follow.
First line of each test case contains N, the number of users with passwords. Second line contains N space separated strings, pass[1] pass[2] \dots pass[N], representing the passwords of each user. Third line contains a string, loginAttempt, for which Yu has to tell whether it will be accepted or not.

1 \le T \le 10
1 \le N \le 10
pass[i] \ne pass[j], 1 \le i \textless j \le N
1 \le length(pass[i]) \le 10, where\ i \in \left[1,N\right]
1 \le length(loginAttempt) \le 2000
loginAttempt and pass[i] contains only lowercase latin characters (‘a’-‘z’).

Output Format
For each valid string, Yu has to print the actual order of passwords, separated by space, whose concatenation results into loginAttempt. If there are multiple solutions, print any of them. If loginAttempt can’t be accepted by the password verification system, then print WRONG PASSWORD.

Sample Input 0

because can do must we what
hello planet
ab abcd cd

Sample Output 0

we do what we must because we can
ab cd

Explanation 0
Sample Case #00: wedowhatwemustbecausewecan is the concatenation of passwords {we, do, what, we, must, because, we, can}. That is

loginAttempt = pass[5] + pass[3] + pass[6] + pass[5] +  pass[4] + pass[1] + pass[5] + pass[2]

Note that any password can repeat any number of times.

Sample Case #01: We can’t create string helloworld using the strings {hello",planet`}.

Sample Case #02: There are two ways to create loginAttempt (abcd). Both pass[2] = "abcd" and pass[1] + pass[3] = "ab cd" are valid answers.

Sample Input 1

ozkxyhkcst xvglh hpdnb zfzahm
gurwgrb maqz holpkhqx aowypvopu
a aa aaa aaaa aaaaa aaaaaa aaaaaaa aaaaaaaa aaaaaaaaa aaaaaaaaaa

Sample Output 1


We can solve this problem recursively and use memoization to avoid running out of time. The basic algorithm goes as follows:
– Iterate over all indices i of loginAttempt:
– Split loginAttempt into two parts left = loginAttempt.substring(0,i) and right = loginAttempt.substring(i).
– Call isValid(left) and isValid(right).
– If both calls return true, then loginAttempt is valid.

Full code

public class PasswordCracker {
    static Set cache; // memoization

    private static boolean isValid(String loginAttempt, Set pass, List out) {
        boolean ans = false;

        if (cache.contains(loginAttempt)) {
            return false;

        if (pass.contains(loginAttempt)) {
            return true;
        } else {

        for (int i = 0; i < loginAttempt.length(); i++) {
            String left = loginAttempt.substring(0, i);
            String right = loginAttempt.substring(i);
            ans = isValid(left, pass, out) && isValid(right, pass, out);
            if (ans) {
                return true;

        return ans;

    public static void main(String[] args) throws FileNotFoundException {
        System.setIn(new FileInputStream(System.getProperty("user.home") + "/" + "in.txt"));
        Scanner in = new Scanner(System.in);

        int tests = in.nextInt();
        for (int t = 1; t <= tests; t++) {
            int n = in.nextInt();
            Set pass = new HashSet();
            for (int i = 0; i < n; i++) {
            String loginAttempt = in.next();

            List out = new LinkedList();
            cache = new HashSet();
            boolean res = isValid(loginAttempt, pass, out);
            if (res) {
                for (String p : out) {
                    System.out.print(p + " ");
            } else {
                System.out.print("WRONG PASSWORD");