CareerCup

One possible Solution using BFS:

String findSecret(String input) {
		Queue<String> queue = new ArrayBlockingQueue<String>((int)Math.pow(2, input.length()+1));
		queue.add("");

		while (true) {
			String lastText = queue.poll();
			if (isTheSecret(lastText))
				return lastText;
			if (input.length() == lastText.length())
				continue;
			String fork1 = lastText + Character.toUpperCase(input.charAt(lastText.length()));
			String fork2 = lastText + Character.toLowerCase(input.charAt(lastText.length()));
			queue.add(fork1);
			queue.add(fork2);
		}
	}

An example of how it works:

public static void main(String args[]) {
		System.out.println(findSecret("abcdefghijklm"));
	}
	
	public static boolean isTheSecret(String input) {
		return input.equals("abCdeFGhiJklM");
	}
	
	public static String findSecret(String input) {
		Queue<String> queue = new ArrayBlockingQueue<String>((int)Math.pow(2, input.length()+1));
		queue.add("");

		while (true) {
			String lastText = queue.poll();
			if (isTheSecret(lastText))
				return lastText;
			if (input.length() == lastText.length())
				continue;
			String fork1 = lastText + Character.toUpperCase(input.charAt(lastText.length()));
			String fork2 = lastText + Character.toLowerCase(input.charAt(lastText.length()));
			queue.add(fork1);
			queue.add(fork2);
		}
	}

Hope this answers your question : )

What's the meaning of a hidden string?
If it is totally hidden, how can we check if it is matched.

One possible Solution using BFS:

String findSecret(String input) {
		Queue<String> queue = new ArrayBlockingQueue<String>((int)Math.pow(2, input.length()+1));
		queue.add("");

		while (true) {
			String lastText = queue.poll();
			if (isTheSecret(lastText))
				return lastText;
			if (input.length() == lastText.length())
				continue;
			String fork1 = lastText + Character.toUpperCase(input.charAt(lastText.length()));
			String fork2 = lastText + Character.toLowerCase(input.charAt(lastText.length()));
			queue.add(fork1);
			queue.add(fork2);
		}
	}

An example of how it works:

public static void main(String args[]) {
		System.out.println(findSecret("abcdefghijklm"));
	}
	
	public static boolean isTheSecret(String input) {
		return input.equals("abCdeFGhiJklM");
	}
	
	public static String findSecret(String input) {
		Queue<String> queue = new ArrayBlockingQueue<String>((int)Math.pow(2, input.length()+1));
		queue.add("");

		while (true) {
			String lastText = queue.poll();
			if (isTheSecret(lastText))
				return lastText;
			if (input.length() == lastText.length())
				continue;
			String fork1 = lastText + Character.toUpperCase(input.charAt(lastText.length()));
			String fork2 = lastText + Character.toLowerCase(input.charAt(lastText.length()));
			queue.add(fork1);
			queue.add(fork2);
		}
	}

Hope this answers your question : )

Just double-clicked the submit button... Sorry for that :(

i think you can just turn both to all lowercase and compare? to use extra O(2^n) time and space just for finding if the hidden string matches a give string doesn't make any sense to me.

Backtracking in C++.

#include <iostream>
#include <cctype>
#include <string>
using namespace std;

void combinations(int depth, string gen, string &S) {
    if (depth == (int)S.size()){
        //check if gen matches hidden string
        cout << gen << endl;
        return;
    }

    combinations(depth + 1, gen + (char)tolower(S[depth]), S);
    combinations(depth + 1, gen + (char)toupper(S[depth]), S);
}

int main(){
    string S;
    cin >> S;
    combinations(0, "", S);
    return 0;
}