happyLadybugs.js

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

function happyLadybugs(b) {
    let hasSpace = false
    const store = {}
    for(const label of b){ // O(n), where n is the length of the string
        if (label === '_'){
            hasSpace = true
            continue
        }
        if(!(label in store)){
            store[label] = 0
        }
        store[label]++
    }
    const hasSingleLabel = Object.values(store).some(val => val === 1)
    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(Object.keys(store).length===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(let i = 0; i < b.length; i++){ // O(n)
        const currLabel = b[i]
        let prevLabel = null
        let nextLabel = null
        if(i-1 >= 0){
            prevLabel = b[i-1]
        }
        if(i+1 < b.length){
            nextLabel = b[i+1]
        }
        
        if(prevLabel!==currLabel && 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)
}