237. Merge Cars Final Arrangement

Merge Cars Final Arrangement

You are given a list of car names and an integer k. Whenever k consecutive cars have the same name, they can be merged into one car with that same name. This merge process can be repeated on the updated list. Return the final arrangement of cars after no more merges are possible.

To keep the output deterministic, always scan the current list from left to right. In one scan, whenever the next k consecutive car names are equal, replace those k cars with one occurrence of the same car name. After performing a merge during a scan, continue scanning immediately after the newly created car. Repeat full scans until the list does not change.

Class

Car Merger

CarMerger()

Creates an object that can merge consecutive cars with the same name.

Methods

Final Arrangement

List<String> finalArrangement(List<String> cars, int k)

Returns the final list of car names after repeatedly merging every k consecutive equal car names.
The relative order of cars that are not merged must remain unchanged.

Constraints

1 ≤ cars.size() ≤ 100,000
2 ≤ k ≤ 100,000
1 ≤ cars.get(i).length() ≤ 30
Each car name contains only uppercase and lowercase English letters.
No parameter value will be null.

Examples

Example 1

finalArrangement(cars = List.of("BMW", "BMW", "Audi", "Audi", "Audi", "Tata"), k = 2)

Output: List.of("BMW", "Audi", "Tata")
The two BMW cars merge into one. The three Audi cars repeatedly merge until one Audi remains.

Example 2

finalArrangement(cars = List.of("Ford", "Ford", "Ford", "Kia", "Kia", "Honda"), k = 3)

Output: List.of("Ford", "Kia", "Kia", "Honda")
The three consecutive Ford cars merge into one. Only two consecutive Kia cars exist, so they cannot merge when k = 3.

Example 3

finalArrangement(cars = List.of("A", "A", "A", "A", "B", "B", "B", "C"), k = 2)

Output: List.of("A", "B", "C")
In the first scan, the four A cars become two A cars, and the three B cars become two B cars.
In the next scan, the two remaining A cars merge into one, and the two remaining B cars merge into one.
The final arrangement is List.of("A", "B", "C").