Happy Ladybugs

See the original problem on HackerRank.

Solutions

This problem can be solved by considering a few things:

  1. if a ladybug's color is unique in the set, the ladybug will never be happy (the solution is “NO”);
  2. if 1) does not occur and if there is at least one empty cell, then the solution is always “YES” since it's always possible to rearrange the ladybugs in the best position;
  3. if 2) does not occur then the solution is “YES” only if all the ladybugs are already happy (because they cannot be moved)

The first two properties are easy to check by using a frequency table (can be implemented with a map/dictionary or with a statically-sized array, since the number of letters is known - \(|A-Z|\)|).

The last property is a linear scan through the array. Basically, we check for each element if it is different from either the previous or the next one.

Here is a possible implementation in C++:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
string happyLadybugs(string s) 
{
    unordered_map<char, int> occ;
    for (auto c : s)
        occ[c]++;
    
    if (count_if(begin(occ), end(occ), [](auto p) { return p.second == 1 && p.first != '_'; }))
        return "NO";
    
    if (occ['_'] != 0)
        return "YES";
    
    for (auto i=0; i<s.size(); ++i)
    {
        if ( (i==0 && s[i] != s[i+1]) || 
             (i==s.size()-1 && s[i] != s[i-1]) || 
             (s[i] != s[i-1] && s[i] != s[i+1]) 
           )
        {
            return "NO";
        }
    }
    return "YES";
}

Here is the same approach in Python:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
def happyLadybugs(n,b):
    hasEmpty = b.count('_') > 0
    for x in b:
        if x != '_' and b.count(x) == 1:
            return "NO"
    if hasEmpty:
        return "YES"
    for i in range(0,n):
        if (i == 0 and b[i] != b[i+1]) or (i == n-1 and b[i] != b[i-1]) or (b[i] != b[i-1] and b[i] != b[i+1]):
            return "NO"   
    return "YES"

Simple variation coded by applying some functional ideas:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
def happyLadybugs(s):
    hasEmpty = b.count('_') > 0
    for x in b:
        if x != '_' and b.count(x) == 1:
            return "NO"
    if hasEmpty:
        return "YES"

    flag = len(s)==1 or (s[0]==s[1] and s[len(s)-2] == s[len(s)-1])   
    zipped = zip(s, s[1:], s[2:])
    return "YES" if flag and all(map(lambda (x1,x2,x3): x2==x1 or x2==x3,  zipped)) else "NO"

Just for fun, the code above can be simplified by adding a fake character both at the beginning and at the end of the string:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
def happyLadybugs(s):
    hasEmpty = b.count('_') > 0
    for x in b:
        if x != '_' and b.count(x) == 1:
            return "NO"
    if hasEmpty:
        return "YES"

    s = '*' + s + '*' # <- fake
    zipped = zip(s, s[1:], s[2:])
    return "YES" if all(map(lambda (x1,x2,x3): x2==x1 or x2==x3,  zipped)) else "NO"

This way, the boundary conditions are automatically handled in the zip | map | reduce part of the solution.

We've worked on this challenge in these gyms: modena 
comments powered by Disqus