Balanced Smileys solution: Facebook hacker Cup 2013 Qual Round

From 2011 facebook is organizing a Facebook hacker cup every year around feb, visit Facebook hacker cup homepage for more details

This question is the second question((Carried 35 marks out of 100) for the qualification round 2013 hacker cup.

Problem Statement

Your friend John uses a lot of emoticons when you talk to him on Messenger. In addition to being a person who likes to express himself through emoticons, he hates unbalanced parenthesis so much that it makes him go 🙁

Sometimes he puts emoticons within parentheses, and you find it hard to tell if a parenthesis really is a parenthesis or part of an emoticon.

A message has balanced parentheses if it consists of one of the following:

• – An empty string “”
• – One or more of the following characters: ‘a’ to ‘z’, ‘ ‘ (a space) or ‘:’ (a colon)
• – An open parenthesis ‘(‘, followed by a message with balanced parentheses, followed by a close parenthesis ‘)’.
• – A message with balanced parentheses followed by another message with balanced parentheses.
• – A smiley face “:)” or a frowny face “:(“

Write a program that determines if there is a way to interpret his message while leaving the parentheses balanced.

Input

The first line of the input contains a number T (1 ≤ T ≤ 50), the number of test cases.
The following T lines each contain a message of length s that you got from John.

Output

For each of the test cases numbered in order from 1 to T, output “Case #i: ” followed by a string stating whether or not it is possible that the message had balanced parentheses. If it is, the string should be “YES”, else it should be “NO” (all quotes for clarity only)

Constraints

• 1 ≤ length of s ≤ 100

Example Input

5
:((
i am sick today (:()
(:)
hacker cup: started :):)
)(

Example Output

Case #1: NO
Case #2: YES
Case #3: YES
Case #4: YES
Case #5: NO

Solution

Before attempting this problem considering smileys, you should first try to do it by ignoring them, how would you solve it without smileys?

One way is keep two counter one for open and one for closed braces, keep increasing and decreasing these counters as you iterate over the list, now as and when you see a closed braces see if openCount -closedCount < 0 => if so they are not balanced. And at the end of the loop openCount should be 0.

But as here happy ‘:)’ and sad ‘:(‘ smileys are included, we have to tweak this approach a bit. At any point of time if openCount – closedCount is negative we should see if there are enough sad smileys to fill the gap. This will consider open braces, closed braces and sad smileys but if @ the end openCount is more we can not be sure if it is unbalanced as there might be few happy smileys in between, but we cant just simply check openCount-happyCount while going from left to right so we have to move from right to left and consider open braces, closed braces and happy smileys. Will be more clear by this java code.

// Save as BalancedSmileys.java 
public class BalancedSmileys {
	public boolean isBalanced(String input) {
		int i = -1;
		
		//First check if there non-allowed characters, not using length knowingly
		try {
			while (true) {
				i++;
				Character c = input.charAt(i);
				if (c < 'a' || c > 'z') {
					if (c != ':' && c != ' ' && c != '(' && c != ')')
						return false;
				}
			}
		} catch (StringIndexOutOfBoundsException e) {
			System.out.println("Reached @ the end of the string");
		}
		// S for Sad emoticon H for happy emoticon */
		input = input.replace(":(", "S");// Sad
		input = input.replace(":)", "H");// Happy

		// Keep only (, ), S and H, replace everything else by empty string */
		input = input.replaceAll("[a-z :]", "");
		System.out.println("Converted Input Str =" + input);

		return isBalancesPerenthesis(input);
	}

	private boolean isBalancesPerenthesis(String input) {
		boolean isBalancedFromLeft = isBalancesPerenthesisFromLeft(input);
		boolean isBalancedFromRight = isBalancesPerenthesisFromRight(input);
		return isBalancedFromLeft && isBalancedFromRight;
	}

	// It only considers sad count, openCount and closedCount */
	private boolean isBalancesPerenthesisFromLeft(String input) {
		int openCount = 0;
		int closedCount = 0;
		int sadCount = 0;
		int happyCount = 0;

		for (Character c : input.toCharArray()) {
			if (c == '(') {
				openCount++;
			} else if (c == ')') {
				closedCount++;
				if (openCount + sadCount - closedCount < 0) {
					return false;
				}
			} else if (c == 'S') {
				sadCount++;
			} else if (c == 'H') {
				happyCount++;
			}
		}
		return true;
	}

	// It only considers happy count, openCount and closedCount */
	private boolean isBalancesPerenthesisFromRight(String input) {
		int openCount = 0;
		int closedCount = 0;
		int sadCount = 0;
		int happyCount = 0;

		for (int i = input.length() - 1; i >= 0; i--) {
			Character c = input.charAt(i);
			if (c == '(') {
				openCount++;
				if (closedCount + happyCount - openCount < 0) {
					return false;
				}
			} else if (c == ')') {
				closedCount++;
			} else if (c == 'S') {
				sadCount++;
			} else if (c == 'H') {
				happyCount++;
			}
		}
		return true;
	}
}

Facebook Comments