# Happy Ladybugs

# Happy Ladybugs

CagkanToptas + 3 comments Dont bother swapping characters until you find a valid string. Here is the trick:

Happy Conditions:

= There are at least one empty cell and there is no Letter with count 1

OR

= There is no empty cell but the given string is happy

shankarpenore + 0 comments thanks brother

Jitendra_sharma + 0 comments yes, u'r right just need to check two conditions:

def happy(n, b): for a in set(b): if a != "_" and b.count(a) == 1: return "NO" if b.count("_") == 0: for i in range(1,n-1): if b[i-1]!=b[i] and b[i+1]!=b[i]: return "NO" return "YES" for _ in range(int(input())): n = int(input()) b = input() print(happy(n, b))

pls like, if this code helps u

aniketnath283 + 0 comments Here is the solution passed for all test cases https://www.hackerrank.com/challenges/happy-ladybugs/forum/comments/491367

jamkin + 8 comments This took me a while to figure out, but after writing out enough cases

/* _ -> YES X -> NO XX -> YES X_ -> NO XY -> NO X_X -> YES XYX -> NO XYZ -> NO _XX -> YES YXX -> NO X__ -> NO X_Y -> NO XXYY -> YES XXYZ -> NO XYXY -> NO XXXY -> NO XYXX -> NO X_XX -> YES X__X -> YES XY_X -> NO X___ -> NO XYZZZ -> NO X_XYY -> YES _XY_Y -> NO _XX__ -> YES _XXYY -> YES X_XYY -> YES X___X -> YES X__YX -> NO X_X_Y_ -> NO XXXYYY -> YES ____ZZ -> YES XYZYZY -> NO XXYYZZ -> YES X_XYXY -> YES (can do moves XX_YXY, XXXY_Y, XXXYY_) XZY_YZX -> YES (can do moves XZ_YYZX, XZZYY_X, _ZZYYXX) _XYYYXX -> YES (can do moves XXYYY_X, XX_YYYX, XXXYYY_) */

I was able to figure out the pattern and derive an algorithm.

// O(n) solution that is meant to be readable but not super-efficient // due to use of LINQ and multiple passes through inputted string. static bool CanMakeAllHappy(string str) { // If there are any non-underscore characters that appear only one // time in the string, they can never be happy. bool existSingles = str.Where(c => c != '_') .GroupBy(c => c).Select(g => g.Count()) .Any(count => count == 1); if(existSingles) return false; // If there are no unhappy characters, return true already. bool existUnhappies = str.Where((c, i) => { if (c == '_') return false; List<char> neighbors = new List<char>(); if (i > 0) neighbors.Add(str[i - 1]); if ((i + 1) < str.Length) neighbors.Add(str[i + 1]); bool isHappy = neighbors.Any(n => n == c); return !isHappy; }) .Any(); if(!existUnhappies) return true; // If we made it here, there are unhappy characters and none of them // appear only one time in the string. So long as there exists an // empty space, we can perform a sequence of swaps that make every // character happy (similar to insertion-sort algorithm). bool existsUnderscores = str.Any(c => c == '_'); return existsUnderscores; }

rich_leigh + 3 comments Thanks for the great set of test cases!

Here they are in custom test case form

37 1 _ 1 X 2 XX 2 X_ 2 XY 3 X_X 3 XYX 3 XYZ 3 _XX 3 YXX 3 X__ 3 X_Y 4 XXYY 4 XXYZ 4 XYXY 4 XXXY 4 XYXX 4 X_XX 4 X__X 4 XY_X 4 X___ 5 XYZZZ 5 X_XYY 5 _XY_Y 5 _XX__ 5 _XXYY 5 X_XYY 5 X___X 5 X__YX 6 X_X_Y_ 6 XXXYYY 6 ____ZZ 6 XYZYZY 6 XXYYZZ 6 X_XYXY 7 XZY_YZX 7 _XYYYXX

and the expected outcome

YES NO YES NO NO YES NO NO YES NO NO NO YES NO NO NO NO YES YES NO NO NO YES NO YES YES YES YES NO NO YES YES NO YES YES YES YES

jan_niklas_koeh1 + 1 comment Thanks that helped alot... why are the two lbugs in testcase 2 (XX) unhappy... both of them have a partner of the same color

andras_szilard + 0 comments That is the third test case ("XX"). The first is "_" and the second is "X".

Ajay_Ravi + 0 comments thanks a lot for your help.....

acc_surajtripat1 + 2 comments i passed all your cases but still i can't pass the test case 8of the website please help.

#include <map> #include <set> #include <list> #include <cmath> #include <ctime> #include <deque> #include <queue> #include <stack> #include <string> #include <bitset> #include <cstdio> #include <limits> #include <vector> #include <climits> #include <cstring> #include <cstdlib> #include <fstream> #include <numeric> #include <sstream> #include <iostream> #include <algorithm> #include <unordered_map> using namespace std; int main(){ int Q; cin >> Q; for(int a0 = 0; a0 < Q; a0++){ int n,count=0,flag=0,count1=0; cin >> n; string b; cin >> b; for(int i=0;i<n;i++) { count=0; if(b[i]=='_') { flag=1; continue; } if(b[i]!='_') { for(int j=0;j<n;j++) { if(b[i]==b[j]) count++; } } if(count==1) { break; } } if(count!=1&&flag==1) {cout<<"YES"<<endl; continue;} else if(flag==0) { for(int i=0;i<n;i+=count1) {count1=0; for(int j=i;b[j]!=b[i],j<n;j++) { if(b[i]==b[j]) count1++; } if(count1==1) { break; } } } if(flag==0&&count1>1) {cout<<"YES"<<endl; continue;} else cout<<"NO"<<endl; } return 0; }

RishabhKejariwal + 0 comments [deleted]RishabhKejariwal + 0 comments The Input which does not works correctly in testcase 8 is:- 10 MY_MMM___ The Output must be NO but your program is giving YES. This error is happening because loop breaks before flag equals 1. So, to fix this first iterate through string and find that does any character is '_' if it is make flag=1.

I am providing you the correct code:-

#include <map> #include <set> #include <list> #include <cmath> #include <ctime> #include <deque> #include <queue> #include <stack> #include <string> #include <bitset> #include <cstdio> #include <limits> #include <vector> #include <climits> #include <cstring> #include <cstdlib> #include <fstream> #include <numeric> #include <sstream> #include <iostream> #include <algorithm> #include <unordered_map> using namespace std; int main(){ int Q; cin >> Q; for(int a0 = 0; a0 < Q; a0++){ int n,count=0,flag=0,count1=0; cin >> n; string b; cin >> b; // I added this for(int i=0;i<n;i++) { if(b[i]=='_') { flag=1; break; } } //Now it works Correctly for(int i=0;i<n;i++) { count=0; /*if(b[i]=='_')// Delete this commented part { flag=1; continue; }*/ if(b[i]!='_') { for(int j=0;j<n;j++) { if(b[i]==b[j]) count++; } } if(count==1) { break; } } if(count!=1&&flag==1) {cout<<"YES"<<endl; continue;} else if(flag==0) { for(int i=0;i<n;i+=count1) {count1=0; for(int j=i;b[j]!=b[i],j<n;j++) { if(b[i]==b[j]) count1++; } if(count1==1) { break; } } } if(flag==0&&count1>1) {cout<<"YES"<<endl; continue;} else cout<<"NO"<<endl; } return 0; }

AAR_KAY + 0 comments Thanks a lot

AAR_KAY + 0 comments [deleted]mitush_k + 0 comments Thanks for the test cases .

zengbabu + 1 comment There is actually something I would like to ask.The case no. 15 ie XYXY is showing YES(it should show NO) and I am at a loss as to how to find out.Could you suggest what could have happened.Thnx in advance. All the rest cases are working fine.

thebick + 0 comments It is a case with no uniques, but no blanks, so no way to rearrange.

So you must go through the string and check for a same value either before or after.

OmShah + 0 comments Upvoted for the test cases.

Ajay_Ravi + 0 comments great work..helped a lot..thanks..

kunalsinghgusain + 0 comments that was the same conclusion I reached after coding for half an hour.

varun_u28 + 1 comment A well broken down solution for the problem

import java.io.*; import java.util.*; import java.text.*; import java.math.*; import java.util.regex.*; public class Solution { public static void main(String[] args) { Scanner in = new Scanner(System.in); int Q = in.nextInt(); for(int a0 = 0; a0 < Q; a0++){ int n = in.nextInt(); String b = in.next(); System.out.println(isHappy(b) ? "YES" : "NO"); } } public static boolean isHappy(String s) { if (hasUnique(s)) { return false; } if (alreadyHappy(s)) { return true; } if (hasSpace(s)) { return true; } return false; } public static boolean hasUnique(String s) { int[] ascii = new int[26]; for (int i=0;i<s.length();i++) { if (s.charAt(i) != '_') { ascii[(int)s.charAt(i)-65]++; } } for (int i=0;i<26;i++) { if (ascii[i] == 1) { return true; } } return false; } public static boolean alreadyHappy(String s) { for (int i=0;i<s.length()-1;i++) { if (i == 0 && s.charAt(i) != s.charAt(i+1)) { return false; } else if (s.charAt(i) != s.charAt(i+1) && s.charAt(i) != s.charAt(i-1)){ return false; } } return true; } public static boolean hasSpace(String s) { for (int i=0;i<s.length();i++) { if (s.charAt(i) == '_') { return true; } } return false; } }

lama199703 + 1 comment [deleted]varun_u28 + 1 comment What I am trying to check here is that if its the first ladybug of the array then it is possible to have only one neighbour. So it can be happy in only 1 condition and that is when the ladybug next to it is of same color. If its of different color or there is a space after it, then it won't be happy.

pardeepsharma_d1 + 0 comments Hi Varun,

I think, there no need of :

if (hasSpace(s)) { return true; }

If you can maintain Underscores count in hasUnique(s) method.

Nice segregation though :)

NYJ1qCr + 1 comment Python 3:

def calculate(n, b): # if b.count("_") == 0 and compare(b): # find if exists any single letter if b.count("_") == 0 and len(re.sub(r'((.)\2+)', "", b)) != 0: return "NO" for a in set(b): if a != "_" and b.count(a) == 1: return "NO" return "YES" ''' Thanks to reddeadya, this part didn't work for "XXBBXX" def compare(b): if len(b) == 1: return True for x in set(b): if x * b.count(x) != b[b.index(x):b.index(x) + b.count(x)]: return True return False ''' for _ in range(int(input())): n = int(input()) b = input() print(calculate(n, b))

reddeadya + 2 comments Beautiful, but why then is input like that calculated as "NO":

1 6 XXBBXX

I suppose initially all ladybugs were happy (cause main condition is satisfied) in this case, am I wrong?

NYJ1qCr + 0 comments [deleted]NYJ1qCr + 1 comment You are right, I didn`t cinsidering this situation. I change my code (function compare(b))ï¼Œuse regular expression:

import re def calculate(n, b): # find if exists any single letter if b.count("_") == 0 and len(re.sub(r'((.)\2+)', "", b)) != 0: return "NO" for a in set(b): if a != "_" and b.count(a) == 1: return "NO" return "YES" for _ in range(int(input())): n = int(input()) b = input() print(calculate(n, b))

more concise! Thanks!

guy_in_catacomb + 1 comment **re.sub(r'((.)\2+)', "", b)**Please describe it. I didn't get it how it is deleting all the same character. I studied about re.sub() but couldn't understand about it.NYJ1qCr + 0 comments The "\2" in r'((.)\2+)' is backreferences, match the same chrarcter as "(.)", which is the second capturing group by count the opening parentheses in regular expression from left to right.

vcardoso + 4 comments I've solved this using an array of the size of alphabet to count the occurrences of each letter. If the count of a letter is one, then it does not have a partner. I also had to deal with the situation where there is no underscores in the input.

Shrey32 + 0 comments [deleted]madhu703 + 0 comments Its awesome. very nice and clear.Thanks

jay1096 + 1 comment vcardoso can I see ur code bcoz I've used the smae approach but mine is not working 2 testcases. Thanks

alihashir4799 + 0 comments Used the same approach but my code doesn,t works.

kasatky + 2 comments C++

int main(){ int Q; cin >> Q; for(int a0 = 0; a0 < Q; a0++){ int n; cin >> n; string b; cin >> b; bool res=1; for(char i='A'; i<='Z'; i++){ int cnt=0; for(int j=0; j<n; j++){ if(b[j]==i) cnt++; } if(cnt==1){res=0; break;} } if(res){ int cnt_=0; for(int i=0; i<n; i++){ if(b[i]=='_') cnt_++; } if(cnt_==0){ for(int i=1; i<(n-1); i++){ if(b[i]!=b[i+1] && b[i]!=b[i-1]) {res=0; break;} } } } if(res) cout << "YES" << endl; else cout << "NO" << endl; } return 0; }

bazuka_ + 0 comments [deleted]codertoaster + 1 comment Better way to count frequency of each Aplhabet in the string and check if there are any spaces.

int letters[]=new int[26]; int n = in.nextInt(); String b = in.next(); boolean space=false; for(int i=0;i<b.length();i++) { if(Character.isLetter(b.charAt(i))) letters[b.charAt(i)-'A']++; else space=true; }

tikhomirovpa + 0 comments Yes, good solution. I did the same on Java. But we still have to check if sequance is already in "happy" condition, because there is a test case in which sequance has not empty positions and has at least pair of each same characters. Without checking on the 'happy' condition, our algorithm doesn't pass this test case

Ariharan_V + 0 comments I figured out as long as there is one '_', and more than one count of same letters, the string is happy. I did few mistakes on edge cases though.

My solution is like:

- If it is single char, then it is happy provided it is '_'.
- In case of two letters, if both are same then happy.
- If there is no '_', then print the state of string.
- If every unique letter in the string appears more than once, they are happy.

O(n)

jpritcha3_14 + 0 comments This is an excellent little problem. It doesn't require any advanced knowledge of algorithms or data structures, but it's a great introduction to edge cases. Took me a while to think through them all :)

sheldonrong + 0 comments My idea is that under the following 2 cases, print NO

- there are no underscore in the string, and there are unhappy bees in the string. (since there are no space to move them around, its not possible to make them happy)
- when there exists one single bee of any kind. (in this case, there is no second bee to match it, even if you have space to move it around, its gonna be unhappy)

in otherwords, as long as there are space to move bees around and all bees have a partner to pair with, its gonna be possible to group them together

solution in python

#!/bin/python3 import sys from collections import Counter def has_unhappy_bees(b): counter = 1 for i in range(0, len(b) - 1): if b[i + 1] == b[i]: counter += 1 else: if counter <= 1: return True return False Q = int(input().strip()) for a0 in range(Q): n = int(input().strip()) b = input().strip() c = Counter(b) if any(1 for k, v in c.items() if v == 1 and k != '_'): print('NO') elif c.get('_', 0) == 0 and has_unhappy_bees(b): print('NO') else: print('YES')

devinludwig + 0 comments ruby:

gets.to_i.times do n = gets.strip.to_i s = gets.strip.chars c = s.group_by{|x| x} happy = true c.each{|k,v| happy = false if v.size < 2 and k != '_'} happy = false if !c['_'] and s.each_with_index.count{|x,i| i>0 and x != s[i-1]} > c.size puts happy ? 'YES' : 'NO' end

Sort 116 Discussions, By:

Please Login in order to post a comment