HackerRank : Week of Code 24 – Happy Ladybugs

By | October 11, 2016

Happy Ladybugs is a board game having the following properties:

  • The board is represented by a string, , of length . The character of the string, , denotes the cell of the board.
    • If is an underscore (i.e., _), it means the cell of the board is empty.
    • If is an uppercase English alphabetic letter (i.e., A through Z), it means the cell contains a ladybug of color .
    • String will not contain any other characters.
  • A ladybug is happy only when its left or right adjacent cell (i.e., ) is occupied by another ladybug having the same color.
  • In a single move, you can move a ladybug from its current position to any empty cell.

Given the values of and for games of Happy Ladybugs, determine if it’s possible to make all the ladybugs happy. For each game, print YES on a new line if all the ladybugs can be made happy through some number of moves; otherwise, print NO to indicate that no number of moves will result in all the ladybugs being happy.

Input Format

The first line contains an integer, , denoting the number of games. The subsequent lines describes a Happy Ladybugs game in the following format:

  1. The first line contains an integer, , denoting the number of cells on the board.
  2. The second line contains a string, , describing the cells of the board.

Constraints

  • It is guaranteed that string consists of underscores and uppercase English alphabetic letters (i.e., _ and Athrough Z).

Output Format

For each game, print YES on a new line if it is possible to make all the ladybugs happy; otherwise, print NO.

Sample Input

4
7
RBY_YBR
6
X_Y__X
2
__
6
B_RRBR

Sample Output

YES
NO
YES
YES

Explanation

The first three games of Happy Ladybugs are explained below:

  1. Initial board:
    lady.png
    After the first move:
    lady(1).png
    After the second move:
    lady(2).png
    After the third move:
    lady(3).png
    Now all the ladybugs are happy, so we print YES on a new line.
  2. There is no way to make the ladybug having color Y happy, so we print NO on a new line.
  3. There are no unhappy ladybugs, so we print YES on a new line.

Solution

Hint: there seems to be nested conditions to check all the scenarios.
My Approach:

I have created one utility function to check if the string contains all same 
characters.

In my main I have written below logical conditions to check :

If string length is 1 & character is Underscore, then output is YES.
If string consists of all same characters, then output is YES.
ELSE:

I have constructed a map and store occurrences of each character and checked
below conditions:

if any character is present only one time other than underscore then output is NO
else, traverse the string and check if there is some character which has no similar 
adjacent
and if there is not even any underscore in the string, then output is NO.


Code for the Solution:

import java.util.HashMap;
import java.util.Map;
import java.util.Map.Entry;
import java.util.Scanner;

public class Solution {
	public static boolean isSame(String str) {
		boolean isSame = true;

		for (int i = 1; i < str.length() - 1; i++) {
			if (str.charAt(i) != str.charAt(i - 1)) {
				isSame = false;
				break;
			}
		}
		return isSame;
	}

	public static void main(String[] args) {
		Scanner scan = new Scanner(System.in);

		int t = scan.nextInt();

		for (int i = 0; i < t; i++) {

			int n = scan.nextInt();
			scan.nextLine();
			String str = scan.nextLine();

			// only one underscore
			if (str.length() == 1 && str.charAt(0) == '_') {
				System.out.println("YES");
			}
			// all same
			else if (isSame(str)) {
				System.out.println("YES");
			} else {

				// construct map

				Map map = new HashMap();
				for (int j = 0; j < n; j++) {
					String s = String.valueOf(str.charAt(j));
					if (map.containsKey(s)) {
						int val = map.get(s);
						val++;
						map.remove(s);
						map.put(String.valueOf(s), val);
					} else {
						map.put(String.valueOf(s), 1);
					}

				}

				// System.out.println(map);

				int flag = 0;
				for (Entry string : map.entrySet()) {

					if (flag == 1)
						break;
					String key = string.getKey();
					int value = string.getValue();

					// underscore is there but any char is only one

					if (value == 1
							&& !string.getKey().equals(String.valueOf('_'))) {
						System.out.println("NO");
						flag = 1;
						break;
					} else {
						for (int g = 1; g < n - 1; g++) {
							if (str.charAt(g) == str.charAt(g - 1)
									|| str.charAt(g) == str.charAt(g + 1)) {
							} else {
								if (str.contains(String.valueOf('_'))) {

								} else {
									if (map.size() == 1) {
									} else {
										System.out.println("NO");
										flag = 1;
										break;
									}

								}
							}
						}
					}

				}
				if (flag == 0)
					System.out.println("YES");

			}

		} // for closes

	}
}