happy_ladybugs.py

# Source: https://www.hackerrank.com/challenges/happy-ladybugs/problem
# Video: https://youtu.be/g9mzmUenrUU

def happyLadybugs(b):
    hasSpace = False
    store = {}
    for label in b: # O(n), where n is the length of the string
        if label == '_':
            hasSpace = True
            continue
        if label not in store:
            store[label] = 0
        store[label] += 1
    
    hasSingleLabel = len([val for val in store.values() if val == 1]) > 0
    if hasSingleLabel:
        return 'NO'
    if hasSpace:
        return 'YES'
    # Past this point, there are NO spaces and all labels have 2+ counts
    # Since we cannot make moves (no spaces), must determine if the 
    # ladybugs are already "happy"
    if len(store) == 1:
        # There is only one label, so no need to check anything else
        return 'YES'
    # Go through each ladybug and check if they're happy
    for i, currLabel in enumerate(b):
        prevLabel = None
        nextLabel = None
        if i - 1 >= 0:
            prevLabel = b[i-1]
        if i + 1 < len(b):
            nextLabel = b[i+1]
        if prevLabel != currLabel and nextLabel != currLabel:
            # If left and right ladybug don't match we can stop checking
            return 'NO'
    # Otherwise, we checked all ladybugs and none were "unhappy"
    return 'YES'
    # Total Time Complexity: O(n) + O(n) => O(n)