Short Problem Definition:
Happy Ladybugs is a board game having the following properties:
- A ladybug is happy only when it’s left or right adjacent cell (i.e., ) b[i+/-1] is occupied by another ladybug having the same color.
time complexity is O(N)
space complexity is O(1)
This challenge definition does not require a full sort. It only wants to know whether the array is sortable. Therefore we will assume that if there is at least one free slot, the array is sortable by color.
Further we will assume that each ladybug wants to have at least one neighbor with the same color. If there are two of the same color, the ladybug is happy.
If there is no empty space, the input array needs to be sorted correctly.
#!/bin/python import math import os import random import re import sys from collections import Counter # Complete the happyLadybugs function below. def happyLadybugs(b): counter = Counter(b) for key, value in counter.items(): if key != "_" and value == 1: return "NO" if "_" in b: return "YES" for idx in xrange(1, len(b)): if b[idx] == b[idx-1] or b[idx] == b[idx+1]: continue else: return "NO" return "YES" if __name__ == '__main__': fptr = open(os.environ['OUTPUT_PATH'], 'w') g = int(raw_input()) for g_itr in xrange(g): n = int(raw_input()) b = raw_input() result = happyLadybugs(b) fptr.write(result + '\n') fptr.close()
If you enjoyed this post, then make sure you subscribe to my Newsletter and/or Feed.