FB HackerCup 2013 QR. https://github.com/anuragkapur/Algorithmic-Programming/tree/master/src/com/anuragkapur/fb/hackercup2013/qr

BalancedSmileysBruteForce.java

public boolean isBalancedMessage(String msg) {

  	boolean isBalanced = true;
		int countSmileys = 0;

		// cleanup message string
		char[] characters = msg.toCharArray();
		StringBuffer cleanedMessageBuffer = new StringBuffer();
		for (int i = 0; i < characters.length; i++) {
			if(characters[i] == '(') {
				if(i != 0) {
					if(characters[i - 1] == ':') {
						// sad smiley
						cleanedMessageBuffer.append("s");
						countSmileys ++;
					}else {
						cleanedMessageBuffer.append("(");
					}
				}else {
					cleanedMessageBuffer.append("(");
				}
			}else if(characters[i] == ')') {
				if(i != 0) {
					if(characters[i - 1] == ':') {
						// happy smiley
						cleanedMessageBuffer.append("h");
						countSmileys ++;
					}else {
						cleanedMessageBuffer.append(")");
					}
				}else {
					cleanedMessageBuffer.append(")");
				}
			}
		}

		// try all permutations of smileys used as a bracket to see if any
		// combination computes to a balanced message
		double maxDecValue= Math.pow(2, countSmileys);

		//System.out.println("maxDecValue :: " + maxDecValue);

		for (int i = 0; i < maxDecValue; i++) {
			isBalanced = true;

			String permuationStr = Integer.toBinaryString(i);
			int paddingLength = countSmileys - permuationStr.length();
			// pad permutation to have a consistent length = noOfBitBinaryCount
			for (int j = 0; j < paddingLength; j++) {
				permuationStr = "0"+permuationStr;
			}

			int indexInPermutationStr = 0;

			// iterate over message and set a smiley to a brace based on permutationStr
			char[] cleanMessageChars = cleanedMessageBuffer.toString().toCharArray();
			for (int j = 0; j < cleanMessageChars.length; j++) {
					if (cleanMessageChars[j] == 's') {
						String permuationBitStr = permuationStr.substring(indexInPermutationStr,indexInPermutationStr+1);
						int permutationBit = Integer.parseInt(permuationBitStr);
						if (permutationBit == 1) {
							cleanMessageChars[j] = '(';
						}
						indexInPermutationStr++;
					}else if(cleanMessageChars[j] == 'h') {
						String permuationBitStr = permuationStr.substring(indexInPermutationStr,indexInPermutationStr+1);
						int permutationBit = Integer.parseInt(permuationBitStr);
						if (permutationBit == 1) {
							cleanMessageChars[j] = ')';
						}
						indexInPermutationStr++;
					}
			}

			// check if a balanced message found
			Stack<Character> balancer = new Stack<Character>();
			for (int j = 0; j < cleanMessageChars.length; j++) {
				if (cleanMessageChars[j] == '(') {
					balancer.push(new Character('('));
				}else if(cleanMessageChars[j] == ')') {
					if (balancer.empty()) {
						isBalanced = false;
					}else {
						balancer.pop();
					}
				}
			}
			if(!balancer.empty()) {
				isBalanced = false;
			}

			if(isBalanced) {
				break;
			}
		}

		return isBalanced;
	}