Here is a very beautiful solution using dynamic programming with $O(n)$ time complexity.
I get a very elegant solution using dynamic programming idea. Just with a $O(n)$ time complexity.
Create a new variable type as
NODE, storing the
left hand sideand
right hand sidebeads with
We cut the necklace into a linear string, then find another one to link it.
Why we do this?
Because we want to find the correct count of left/right hand side beads.
What will happen if there is just one necklace not two?
Then think about the bead count on the left or right side.
Left side end cannot count
left hand sidebeads, although it should be a rounded necklace rather than a linear string.
It is the same for the
right hand sidebeads.
From left to right, count the
left hand sidebeads with dp transform function:
if beads[i - 1] == 'r'
neck[i].left_hand_side_blue_num = 0
and neck[i].left_hand_side_red_num = neck[i - 1].left_hand_side_red_num
if beads[i - 1] == 'b'
neck[i].left_hand_side_red_num = 0
and neck[i].left_hand_side_blue_num = neck[i - 1].left_hand_side_blue_num
From right to left, count the
right hand sidebeads with dp transform function. (you can think about it, read the code, or see the dp transform function I wrote for left to right direction)
Finally, let’s count!
Remember that there only need to read
beads_num - 1times, since we only need to count one end for one direction, so we omitted the other end.
left hand sidecount need only considering the left side of the string, from
bead_num + 1to
2 * bead_num - 1.
right hand sidecount only consider the right side of string, from 0 to
beads_num - 1.