/* 
 
_       -> 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_)
    */

// 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;
    }