# Happy Ladybugs

# Happy Ladybugs

CagkanToptas + 7 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 + 1 comment thanks brother

paviipavii1991 + 1 comment How did you arrive at this conclusion?

jasontank + 0 comments 1) If you don't have at least one blank space, no swapping can happen. 2) If there's only one of a certain color of ladybug, it can never find a partner and be happy.

qwrtyuiuytres + 2 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

shubhamkashyap + 1 comment BAAAB The answer should be NO.

bhushanoffone + 0 comments [deleted]

trojan1729 + 1 comment A good solution. A bit of optimisation to your code is to iterate through the list once and store the characters as keys opposed to their count as values in a dict(). This avoids the list.count going O(n) for each character and hence avoids O(n^2) solution. Food for thought.

josef_klotzner + 0 comments Even faster than using a dict is to use a "count list" with index ord (char) - 65. So this list starts with ord ("A") - 65 = 0. O (1) instead of O (log n) for access to count of char. Here my solution: https://www.hackerrank.com/challenges/happy-ladybugs/submissions/code/109012363

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

aratnawat002 + 0 comments [deleted]aratnawat002 + 0 comments [deleted]CS18B056 + 0 comments superr

hrshtvrm + 0 comments I came up with the same thing :)

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 + 6 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; }

shjang + 0 comments Thanks a lot. These test cases were very helpful to have test.

pappy_o + 1 comment Thanks so much for this! I'm passing all of these but still failing TC3 (unlocking with Hackos was virtually worthless because everything is truncated and there is no option to download the full output to see where I'm failing). Anyone know of another way to view the complete test case on failed submissions?

pappy_o + 0 comments Ah, nevermind. For those also experiencing this, check to make sure you aren't being trolled by content colors :) (the downlaod link is there, just tough to see).

pappy_o + 0 comments One more test case to add to your fabulous list:

The ladybugs are happy without any swaps, but there are different numbers of them.

1 5 XXYYY

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 + 3 comments 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 :)

shubhamkashyap + 0 comments In alreadyhappy function if the test case is like BBAAAB ur function is not checking what happens when i=s.length()-1.

rohitpal210 + 0 comments [deleted]

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.

JuanDavidCanti + 0 comments My Java Solution

static String happyLadybugs(String b) { int[] lb = new int['Z' - 'A' + 1]; boolean esp = false; //The number of ladybirds for each color is saved in lb //and evaluated if there is at least one space for (char c : b.toCharArray()) { if(c!='_'){ lb[c-'A']++; }else{ esp = true; } } //If there are no spaces, all the ladybugs should have an equal partner if (!esp) { for (int i = 1; i < b.length()-1; i++) { if(b.charAt(i)!=b.charAt(i-1) && b.charAt(i)!=b.charAt(i+1)){ return "NO"; } } } //If there are spaces, there can not be a ladybug of a single color for (int i : lb) { if(i==1) return "NO"; } //If there is no unhappy ladybug return "YES"; }

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)

klinMlin + 0 comments static boolean f1(String str) { int underscore=0; int[] abc = new int[26]; for(int i=0;i<str.length();i++) { if(str.charAt(i)!='_') abc[str.charAt(i)-'A']++; else underscore++; } for(int i=0;i<abc.length;i++) if(abc[i]==1) return false; return underscore==0?false:true; } static String happyLadybugs(String b) { String pattern="((\\w)\\2+)+\\_?"; if(b.matches(pattern) || f1(b)) return "YES"; return "NO"; }

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 :)

Sort 175 Discussions, By:

Please Login in order to post a comment