A town festival sets up food-and-craft vendor stalls on a grid, with the plaza's flagpole fixed at coordinate (0, 0). Each vendor stall sits at an integer coordinate (x, y), never at the flagpole itself, and carries a licence category code (an uppercase string). No two stalls share the exact same coordinate.
The organizer wants to rope off a square zone around the flagpole: an axis-aligned square centered at (0, 0) with sides parallel to the grid axes, whose half-width she may choose freely (any non-negative value). A stall lies inside the zone exactly when both |x| and |y| for that stall are at most the zone's half-width. The zone may only be opened if every stall inside it has a licence category different from every other stall inside it -- no two roped-in stalls may share a category code.
Help the organizer pick a half-width that maximizes the number of stalls she can rope in while keeping every included category distinct.
A single integer: the maximum number of stalls that can be roped into one valid square zone.
Example 1
Input
4 0 1 X 2 0 Y 0 -2 Z 5 0 X
Expected
3
Explanation
Distances from the flagpole are 1 (category X), 2 (category Y), 2 (category Z), and 5 (category X). Growing the zone to half-width 1 includes only X, which is fine. Growing to half-width 2 also pulls in Y and Z, both new categories, so the total is now 3 with no conflict. Growing further to half-width 5 would add a second X, which repeats a category already inside, so the zone must stop at half-width 2. The maximum is 3 stalls.
Example 2
Input
4 1 0 X 0 1 X 0 -1 Y 3 0 Z
Expected
0
Explanation
The two closest stalls sit at distance 1: (1, 0) tagged X and (0, 1) also tagged X. That category already collides within the very first, smallest-distance group, so no non-empty zone can be opened without a duplicate category. The answer is 0.
Ready to solve this?
Sign in to open the editor, run your code against the sample tests, and submit against the full test suite.
Sign in to solve →