An EV charging station has a row of charging bays along a one-way lane. Each bay supports one connector type, represented by a lowercase English letter.

A fleet of electric vehicles enters the lane in a fixed order. Each vehicle requires a particular connector type, which is also represented by a lowercase English letter.

The connector requirements of the vehicles are given by vehicleNeeds. The supported connector types of the charging bays, from left to right, are given by chargerTypes.

Every vehicle must be assigned to a compatible charging bay. Because the lane is one-way and vehicles cannot overtake, their assigned bay positions must follow the same order in which the vehicles appear in vehicleNeeds.

The gap between two consecutive vehicles is the number of unoccupied charging bays strictly between their assigned bays.

Find the maximum gap that can occur between any two consecutive vehicles in any valid assignment.

Class

EVChargingBayPlanner

Method

maximumFreeBayGap

public int maximumFreeBayGap(String vehicleNeeds, String chargerTypes)

• vehicleNeeds contains the required connector type of each vehicle in arrival order.
• chargerTypes contains the supported connector type of each charging bay from left to right.
• Returns the maximum possible number of unoccupied charging bays between two consecutive vehicles.

Rules

• A vehicle can only use a charging bay whose connector type matches its required connector type.
• Each charging bay can be assigned to at most one vehicle.
• Every vehicle must be assigned exactly one charging bay.
• The assigned bay positions must be strictly increasing according to the order of the vehicles.
• The assigned charging bays do not need to be consecutive.
• If two consecutive vehicles are assigned to positions leftPosition and rightPosition, their gap is rightPosition - leftPosition - 1.
• Unoccupied bays before the first assigned vehicle or after the last assigned vehicle are not included in any gap.
• If there is only one vehicle, return 0.
• At least one valid assignment is guaranteed to exist.

Constraints

• 1 ≤ vehicleNeeds.length() ≤ chargerTypes.length() ≤ 200,000
• vehicleNeeds and chargerTypes contain only lowercase English letters.
• vehicleNeeds is a subsequence of chargerTypes.
• The solution must run in O(vehicleNeeds.length() + chargerTypes.length()) time.

Examples

Example 1

maximumFreeBayGap(vehicleNeeds = "ctc", chargerTypes = "cctaaac")

Output: 3

The vehicles can use the first, third, and seventh charging bays. There is one unoccupied bay between the first two vehicles and three unoccupied bays between the final two vehicles. Therefore, the maximum gap is 3.

Example 2

maximumFreeBayGap(vehicleNeeds = "nn", chargerTypes = "nccccn")

Output: 4

The vehicles can use the first and sixth charging bays. The four bays between them remain unoccupied.

Example 3

maximumFreeBayGap(vehicleNeeds = "ctn", chargerTypes = "ctn")

Output: 0

Every charging bay must be used, so there is no unoccupied bay between consecutive vehicles.

Example 4

maximumFreeBayGap(vehicleNeeds = "t", chargerTypes = "ccctcc")

Output: 0

Only one vehicle needs a charging bay, so there is no pair of consecutive vehicles.