Rightward Bacteria Consumption
Learn this problem
CrestaFULLTIMEOAProblem statement
Bacteria stand from left to right. The string types gives each bacterium's type, and sizes[i] gives its fixed size. Process bacteria from left to right while maintaining the bacteria that have survived so far.
When the next bacterium is processed, compare it only with the nearest surviving bacterium to its left. That left bacterium immediately consumes the new bacterium exactly when the left bacterium is larger and their types differ. Consumption does not change the eater's size. If the condition is false, the new bacterium also survives.
Return the original zero-based indices of all surviving bacteria in left-to-right order.
Function
survivingBacteria(types: String, sizes: int[]) → int[]Examples
Example 1
types = "ABCD"sizes = [9,4,7,2]return = [0]The bacterium at index 0 is larger than every later bacterium and has a different type from each, so it consumes indices 1, 2, and 3.
Example 2
types = "ABCA"sizes = [5,7,3,2]return = [0,1]Index 0 cannot consume the larger bacterium at index 1. Index 1 then consumes indices 2 and 3, leaving indices 0 and 1.
Example 3
types = "AABC"sizes = [10,1,2,1]return = [0,1,2]Index 0 and index 1 have the same type, so both survive. Index 1 is too small to consume index 2, which also survives and then consumes index 3.
Constraints
1 <= types.length == sizes.length <= 10^5.- Every character of
typesisA,B,C, orD. 1 <= sizes[i] <= 10^9.- A bacterium's size never changes after consumption.
- Equal-size or equal-type neighboring survivors do not consume one another.