s consists only of lowercase English letters.

Solution

Method 1 – Binary Search with Hashing

Intuition

We want to find the largest square (centered at the origin) that contains the maximum number of points, with the restriction that no two points inside the square have the same tag. Since the square is axis-aligned and centered at (0,0), we can use binary search on the possible side length, and for each candidate, check if it's possible to select points with unique tags inside the square.

Approach

Define a helper function to check if a square of side 2 * d (from -d to d) can contain a set of points with unique tags.
Use binary search on d (the half-side length) from 0 up to the maximum absolute coordinate in points.
For each d, collect all points within the square and check if their tags are unique (using a set or map).
Track the maximum number of unique-tagged points found for any valid d.
Return the maximum number found.

Code

[{"language":"C++","code":"class Solution {\npublic:\n    int maxPointsInsideSquare(vector<vector<int>>& points, string s) {\n        int n = points.size();\n        int l = 0, r = 0, ans = 0;\n        for (auto& p : points) r = max(r, max(abs(p[0]), abs(p[1])));\n        while (l <= r) {\n            int d = (l + r) / 2;\n            unordered_set<char> tags;\n            int cnt = 0;\n            bool valid = true;\n            for (int i = 0; i < n; ++i) {\n                if (abs(points[i][0]) <= d && abs(points[i][1]) <= d) {\n                    if (tags.count(s[i])) { valid = false; break; }\n                    tags.insert(s[i]);\n                    cnt++;\n                }\n            }\n            if (valid) {\n                ans = max(ans, cnt);\n                l = d + 1;\n            } else {\n                r = d - 1;\n            }\n        }\n        retur

Related Tags