Solution
Approach 1: Greedy
Intuition
Intuitively, we should write the most common letter first. For example, if we have A = 6, B = 2
, we want to write 'aabaabaa'
. The only time we don't write the most common letter is if the last two letters we have written are also the most common letter
Algorithm
Let's maintain A, B
: the number of 'a'
and 'b'
's left to write.
If we have already written the most common letter twice, we'll write the other letter. Otherwise, we'll write the most common letter.
Complexity Analysis

Time Complexity: .

Space Complexity: .
Analysis written by: @awice.