Challenge I saw on HackerNews, "Most candidates cannot solve this interview problem."

MostCandidatesFail.hs

{-
I saw this posted on HackerNews:

"Most candidates cannot solve this interview problem."

https://twitter.com/Al_Grigor/status/1357028887209902088

> Most candidates cannot solve this interview problem:
> Input: "aaaabbbcca"
> Output: [("a", 4), ("b", 3), ("c", 2), ("a", 1)]

I honestly solved it very quickly with Haskell! So I thought
I would do a few methods.
-}

import Data.List (group)
import Control.Arrow ((&&&))

theInput = "aaaabbbcca"
expectedOutput = [('a', 4), ('b', 3), ('c', 2), ('a', 1)] 

-- First solution. I was able to do this very quickly (under a couple minutes).
firstSolution = map (\x -> (head x, length x)) . group

-- This solution took a while longer because I accidentally messed up a pattern match!
-- The point of this solution was to implement group myself.
secondSolution =
  map (\x -> (head x, length x)) $ reverse $ foldl (\acc x -> appendToGroup x acc) [] theInput
 where
  appendToGroup :: Eq a => a -> [[a]] -> [[a]]
  appendToGroup x (g:gs) = if x `elem` g then (x:g):gs else [x]:g:gs
  appendToGroup x [] = [[x]]

-- I thought of this solution later on because I recently used this function...
thirdSolution = map (head &&& length) . group

-- My friend challenged me to do this without using any "fancy" functions.
startSolution4 (x:xs) = solution4 xs (x, 1) []
 where
  solution4 (x:xs) (c, i) acc 
    | x == c = solution4 xs (c, i + 1) acc 
    | otherwise =  solution4 xs (x, 1) (acc ++ [(c, i)])
  solution4 [] (c, i) as = as ++ [(c, i)]