https://leetcode.com/discuss/interview-question/1581861/microsoft-oa-longest-alternating-path

Is there a O(n) time solution for this?