We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
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.staticboolCanMakeAllHappy(stringstr){// If there are any non-underscore characters that appear only one// time in the string, they can never be happy.boolexistSingles=str.Where(c=>c!='_').GroupBy(c=>c).Select(g=>g.Count()).Any(count=>count==1);if(existSingles)returnfalse;// If there are no unhappy characters, return true already.boolexistUnhappies=str.Where((c,i)=>{if(c=='_')returnfalse;List<char>neighbors=newList<char>();if(i>0)neighbors.Add(str[i-1]);if((i+1)<str.Length)neighbors.Add(str[i+1]);boolisHappy=neighbors.Any(n=>n==c);return!isHappy;}).Any();if(!existUnhappies)returntrue;// 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).boolexistsUnderscores=str.Any(c=>c=='_');returnexistsUnderscores;}
Happy Ladybugs
You are viewing a single comment's thread. Return to all comments →
This took me a while to figure out, but after writing out enough cases
I was able to figure out the pattern and derive an algorithm.