Problem

You are given a 2D**** array points and a string s where, points[i] represents the coordinates of point i, and s[i] represents the tag of point i.

A valid square is a square centered at the origin (0, 0), has edges parallel to the axes, and does not contain two points with the same tag.

Return the maximum number of points contained in a valid square.

Note:

  • A point is considered to be inside the square if it lies on or within the square’s boundaries.
  • The side length of the square can be zero.

Examples

Example 1

 1
 2
 3
 4
 5
 6
 7
 8
 9
10


![](https://assets.leetcode.com/uploads/2024/03/29/3708-tc1.png)

Input: points = [[2,2],[-1,-2],[-4,4],[-3,1],[3,-3]], s = "abdca"

Output: 2

Explanation:

The square of side length 4 covers two points `points[0]` and `points[1]`.

Example 2

 1
 2
 3
 4
 5
 6
 7
 8
 9
10


![](https://assets.leetcode.com/uploads/2024/03/29/3708-tc2.png)

Input: points = [[1,1],[-2,-2],[-2,2]], s = "abb"

Output: 1

Explanation:

The square of side length 2 covers one point, which is `points[0]`.

Example 3

1
2
3
4
5
6
7
8
9


Input: points = [[1,1],[-1,-1],[2,-2]], s = "ccd"

Output: 0

Explanation:

It's impossible to make any valid squares centered at the origin such that it
covers only one point among `points[0]` and `points[1]`.

Constraints

  • 1 <= s.length, points.length <= 10^5
  • points[i].length == 2
  • -109 <= points[i][0], points[i][1] <= 10^9
  • s.length == points.length
  • points consists of distinct coordinates.
  • 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

  1. 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.
  2. Use binary search on d (the half-side length) from 0 up to the maximum absolute coordinate in points.
  3. For each d, collect all points within the square and check if their tags are unique (using a set or map).
  4. Track the maximum number of unique-tagged points found for any valid d.
  5. Return the maximum number found.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

class Solution {
public:
    int maxPointsInsideSquare(vector<vector<int>>& points, string s) {
        int n = points.size();
        int l = 0, r = 0, ans = 0;
        for (auto& p : points) r = max(r, max(abs(p[0]), abs(p[1])));
        while (l <= r) {
            int d = (l + r) / 2;
            unordered_set<char> tags;
            int cnt = 0;
            bool valid = true;
            for (int i = 0; i < n; ++i) {
                if (abs(points[i][0]) <= d && abs(points[i][1]) <= d) {
                    if (tags.count(s[i])) { valid = false; break; }
                    tags.insert(s[i]);
                    cnt++;
                }
            }
            if (valid) {
                ans = max(ans, cnt);
                l = d + 1;
            } else {
                r = d - 1;
            }
        }
        return ans;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

func maxPointsInsideSquare(points [][]int, s string) int {
    n := len(points)
    l, r, ans := 0, 0, 0
    for _, p := range points {
        if abs(p[0]) > r { r = abs(p[0]) }
        if abs(p[1]) > r { r = abs(p[1]) }
    }
    for l <= r {
        d := (l + r) / 2
        tags := make(map[byte]bool)
        cnt := 0
        valid := true
        for i := 0; i < n; i++ {
            if abs(points[i][0]) <= d && abs(points[i][1]) <= d {
                if tags[s[i]] { valid = false; break }
                tags[s[i]] = true
                cnt++
            }
        }
        if valid {
            if cnt > ans { ans = cnt }
            l = d + 1
        } else {
            r = d - 1
        }
    }
    return ans
}
func abs(x int) int { if x < 0 { return -x }; return x }
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

class Solution {
    public int maxPointsInsideSquare(int[][] points, String s) {
        int n = points.length, l = 0, r = 0, ans = 0;
        for (int[] p : points) r = Math.max(r, Math.max(Math.abs(p[0]), Math.abs(p[1])));
        while (l <= r) {
            int d = (l + r) / 2;
            Set<Character> tags = new HashSet<>();
            int cnt = 0;
            boolean valid = true;
            for (int i = 0; i < n; ++i) {
                if (Math.abs(points[i][0]) <= d && Math.abs(points[i][1]) <= d) {
                    if (tags.contains(s.charAt(i))) { valid = false; break; }
                    tags.add(s.charAt(i));
                    cnt++;
                }
            }
            if (valid) {
                ans = Math.max(ans, cnt);
                l = d + 1;
            } else {
                r = d - 1;
            }
        }
        return ans;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

class Solution {
    fun maxPointsInsideSquare(points: Array<IntArray>, s: String): Int {
        var l = 0
        var r = 0
        var ans = 0
        for (p in points) r = maxOf(r, kotlin.math.abs(p[0]), kotlin.math.abs(p[1]))
        while (l <= r) {
            val d = (l + r) / 2
            val tags = mutableSetOf<Char>()
            var cnt = 0
            var valid = true
            for (i in points.indices) {
                if (kotlin.math.abs(points[i][0]) <= d && kotlin.math.abs(points[i][1]) <= d) {
                    if (tags.contains(s[i])) { valid = false; break }
                    tags.add(s[i])
                    cnt++
                }
            }
            if (valid) {
                ans = maxOf(ans, cnt)
                l = d + 1
            } else {
                r = d - 1
            }
        }
        return ans
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

class Solution:
    def maxPointsInsideSquare(self, points: list[list[int]], s: str) -> int:
        l, r, ans = 0, 0, 0
        for x, y in points:
            r = max(r, abs(x), abs(y))
        n = len(points)
        while l <= r:
            d = (l + r) // 2
            tags = set()
            cnt = 0
            valid = True
            for i in range(n):
                if abs(points[i][0]) <= d and abs(points[i][1]) <= d:
                    if s[i] in tags:
                        valid = False
                        break
                    tags.add(s[i])
                    cnt += 1
            if valid:
                ans = max(ans, cnt)
                l = d + 1
            else:
                r = d - 1
        return ans
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

impl Solution {
    pub fn max_points_inside_square(points: Vec<Vec<i32>>, s: String) -> i32 {
        let mut l = 0;
        let mut r = 0;
        let mut ans = 0;
        for p in &points {
            r = r.max(p[0].abs()).max(p[1].abs());
        }
        let n = points.len();
        let s = s.as_bytes();
        while l <= r {
            let d = (l + r) / 2;
            let mut tags = std::collections::HashSet::new();
            let mut cnt = 0;
            let mut valid = true;
            for i in 0..n {
                if points[i][0].abs() <= d && points[i][1].abs() <= d {
                    if tags.contains(&s[i]) { valid = false; break; }
                    tags.insert(s[i]);
                    cnt += 1;
                }
            }
            if valid {
                ans = ans.max(cnt);
                l = d + 1;
            } else {
                r = d - 1;
            }
        }
        ans
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

class Solution {
    maxPointsInsideSquare(points: number[][], s: string): number {
        let l = 0, r = 0, ans = 0;
        for (const [x, y] of points) r = Math.max(r, Math.abs(x), Math.abs(y));
        const n = points.length;
        while (l <= r) {
            const d = Math.floor((l + r) / 2);
            const tags = new Set<string>();
            let cnt = 0;
            let valid = true;
            for (let i = 0; i < n; ++i) {
                if (Math.abs(points[i][0]) <= d && Math.abs(points[i][1]) <= d) {
                    if (tags.has(s[i])) { valid = false; break; }
                    tags.add(s[i]);
                    cnt++;
                }
            }
            if (valid) {
                ans = Math.max(ans, cnt);
                l = d + 1;
            } else {
                r = d - 1;
            }
        }
        return ans;
    }
}

Complexity

  • ⏰ Time complexity: O(n log M), where n is the number of points and M is the maximum absolute coordinate value. Each binary search step checks all points.
  • 🧺 Space complexity: O(n), for the set of tags in the worst case.