Intro
In this article, we tackle Leet2038 here like Casemiro tackled Bruno Fernandes two weeks ago (or years ago depending on when you're reading this 😂😂😂). The problem presents a gaming scenario where we're given a sequence of game pieces/items, each colored either 'A' or 'B'. Imagine a board game between Alice and Bob, where they take turns removing pieces based on certain rules. The goal of Leet2038 is simple: determine who wins this delightful game! Alice? Bob?
The problem is a kind of weird one. Weird because it is actually quite easy to implement. It does not build on any complex algorithmic pattern or data structures. I think, literally the barest minimum of programming knowledge is required to solve this. However, it is very easy to overcomplicate the problem and get stuck especially since it is tagged a medium difficulty. I know I did.
Problem Statement
There are n pieces arranged in a line and each piece is colored either by 'A' or by 'B'. You are given a string colors of length n where colors[i] is the color of the i<sup>th</sup> piece.
Alice and Bob are playing a game where they take alternating turns removing pieces from the line. In this game, Alice moves first.
Alice is only allowed to remove a piece colored 'A' if both its neighbors are also colored 'A'. She is not allowed to remove pieces that are colored 'B'.
Bob is only allowed to remove a piece colored 'B' if both its neighbors are also colored 'B'. He is not allowed to remove pieces that are colored 'A'.
Alice and Bob cannot remove pieces from the edge of the line.
If a player cannot make a move on their turn, that player loses and the other player wins.
Assuming Alice and Bob play optimally, return true if Alice wins, or return false if Bob wins.
Initial Thought
We will skip this, it's embarrassing. I was actually stuck because I started thinking of how to track how many times Bob can possibly win individually (i.e how many times we have a substring of 3 consecutive Bs, and what happens when have 4, 5,...+ Bs), and how many times Alice can possibly win individually. maybe that could work but It was evident after some minutes that it was after all an overkill and would be tricky to implement even if it could work.
how do we solve it then?
1. I reread and tried to simplify the question so I could completely understand it.
2. I walked through the test cases manually without writing down any code
3. I realized it has a lot to do with sequencing. so, I decided; solve an easy Leet whatever that implements sequencing, let's call that a detour.
The Detour
Problem Statement:
Given a binary array nums, return the maximum number of consecutive 1's in the array.
Example
Input: nums = [1,1,0,1,1,1]
Output: 3
Explanation: The first two digits or the last three digits are
consecutive 1s. The maximum number of consecutive 1s is 3.
Solution:
import "math"
func findMaxConsecutiveOnes(nums []int) int {
max ,curr := 0,0;
for _,num := range nums{
if num == 1{
curr++
}else{
max = int(math.Max(float64(max), float64(curr)))
curr=0
}
}
max = int(math.Max(float64(max), float64(curr)))
return max;
}
this problem had to do with counting number of similar elements except this problem is even a little more complex because now, we have to know when to reset the current counts
My Approach
Let's read the problem again because really, that is the only difficult part.
Givens:
1. Alice can only remove a piece provided both its neighbors are the same. I.E 'AAA'
2. Bob can only remove a piece if both its neighbors are the same. I.E 'BBB'
what the above might tell us is that we have to loop through the string and check at every point in time if we have 3 consecutive colors. (think of what that logic will look like in your head. i-1 , i and i+1 right? yh, you might be right.)
but.....
3. What if we have an instance where we have 4 consecutive? ('AAAA').
hmmm. well, it barely matters because we only need to know and worry about checking that there will be 3 consecutive AAA, and if we move to the next iteration, We verify this condition AGAIN, which signals that we can perform two removals consecutively from that position. and that is accurate for 4 consecutive As. The same logic works if there are even more.
Counting the occurrences essentially tells us how many times a player can make a move in the game, independently of whether there's another player or not.
4. A player cannot remove pieces at the edge, sweet. I guess we better start counting from index 1 and end at (index array.length -2). This also tells us the least length of the array we can possibly get us 2. I guess 🤡.
- Alice plays first. so, if they both end up with an equal number of moves, Alice loses. I really should not have to explain that part.
💡
To Summarize, the trick behind solving this problem is looking for how many moves either of them possibly have. and because Alice played first, Alice must have a higher number to win. else she loses.
Implementation
solving this in go since it is quite straightforward
func winnerOfGame(colors string) bool {
aCount := 0
bCount := 0
n := len(colors)
for i := 1; i < n-1; i++ {
if colors[i] == 'A' {
if colors[i-1] == 'A' && colors[i+1] == 'A' {
aCount++
}
} else if colors[i] == 'B' {
if colors[i-1] == 'B' && colors[i+1] == 'B' {
bCount++
}
}
}
return aCount > bCount
}
Complexity Analysis
Nothing to analyze here
Time complexity: O(n) ~ Linear
Space Complexity: O(1) Constant
Takeaways/ Lessons
This question really tests how you can convert business logic into code and simplify problems. It really is a simple problem and you would easily be wasting company's time and resources if you are unable to see that
Also, don't jump heading into solving questions. when stuck, try to solve manually with test cases and not programmatically.
Conclusion
In tackling Leet2038, we've learned that even seemingly simple problems can test our ability to simplify and implement business logic effectively. The key is recognizing the essence of the problem and avoiding unnecessary complexity. The essence was simply who wins. every other variable (E.G how many times a player can remove from a consecutive subsequence) is unnecessary if they do not help us achieve our result.
