A row contains occupied and unoccupied seats. Each seat is represented by "O" when occupied or "U" when unoccupied.

Find the unoccupied seat whose distance from its nearest occupied seat is as large as possible. The distance between two seats is the absolute difference between their zero-based positions.

If multiple unoccupied seats have the same maximum distance, return the smallest position among them.

Class

SeatDistanceFinder

Constructor

SeatDistanceFinder

SeatDistanceFinder()

• Creates a new seat distance finder.

Method

findSeatPosition

int findSeatPosition(List<String> seats)

• seats.get(i) represents the seat at zero-based position i.
• Returns the position of the unoccupied seat that maximizes the distance to its nearest occupied seat.

Rules

• "O" represents an occupied seat.
• "U" represents an unoccupied seat.
• For an unoccupied seat at position i, its distance is the minimum value of abs(i - j) over all occupied positions j.
• When several seats have the same maximum distance, the seat with the smallest position must be returned.
• The input list must not be modified.

Constraints

• 2 ≤ seats.size() ≤ 100,000
• Every element of seats is either "O" or "U".
• At least one seat is occupied.
• At least one seat is unoccupied.
• seats and all its elements are non-null.

Expected Efficiency

• The method should run in O(n) time.
• The method should use O(1) additional space.

Example 1

findSeatPosition( seats = List.of("U", "U", "O", "U", "U", "U", "O", "U"))

Output: 0

Positions 0 and 4 are both two seats away from their nearest occupied seat. Position 0 is returned because it is smaller.

Example 2

findSeatPosition( seats = List.of("O", "U", "O", "U", "U", "U", "U"))

Output: 6

Position 6 is four seats away from the nearest occupied seat, which is farther than every other unoccupied seat.

Example 3

findSeatPosition( seats = List.of("U", "O", "U", "U", "U", "O", "U"))

Output: 3

Position 3 is two seats away from its nearest occupied seat.