Largest Microorganism After Consumption
Problem statement
Microorganisms are arranged from left to right. Microorganism i has family families[i] and positive size sizes[i].
The simulation proceeds in rounds. At the start of each round, every surviving microorganism is eligible to participate once. Scan the current line from left to right:
- If the current microorganism and its immediate left neighbor have not participated this round, the left neighbor belongs to a different family, and the left neighbor is strictly smaller, the current microorganism eats the left neighbor.
- Otherwise, if the current microorganism and its immediate right neighbor have not participated this round, the right neighbor belongs to a different family, and the right neighbor is strictly smaller, the current microorganism eats the right neighbor.
- Otherwise, it does nothing.
When one microorganism eats another, the eater gains the target's size, the target disappears, and the eater cannot participate again in that round. Earlier removals immediately change which microorganisms are adjacent.
Stop when a complete round performs no consumption. The final line is guaranteed to contain exactly one microorganism whose size is strictly greater than every other survivor. Return its family, one space, and its size.
Function
largestMicroorganism(families: String[], sizes: int[]) → StringExamples
Example 1
families = ["A","B","C"]sizes = [3,1,2]return = "A 6"In the first round, A eats B and grows to 4. In the next round, A eats C and grows to 6.
Example 2
families = ["A","B","C","D"]sizes = [2,5,1,4]return = "B 12"During the first round, B eats A and D eats C. Then B consumes D.
Example 3
families = ["X","Y","Z"]sizes = [3,3,1]return = "Y 7"Equal-sized neighbors cannot eat each other. Y first eats Z, grows to 4, and then eats X in the next round.
Example 4
families = ["A","B","C","B","B","A","C"]sizes = [5,5,2,10,4,6,7]return = "A 39"The successive round sizes are [5,7,10,10,7], [12,10,17], [12,27], and [39]. The associated families are [A,B,B,A,C], [B,B,A], [B,A], and [A].
Example 5
families = ["A","A"]sizes = [7,2]return = "A 7"Both organisms belong to the same family, so neither may consume the other. The unique maximum stays A 7.
Constraints
1 ≤ families.length = sizes.length ≤ 20- Every family is a nonempty string without spaces.
1 ≤ sizes[i] ≤ 10^6- The final survivors have one unique maximum size.