4021. Distinct Points Reachable After Substring Removal¶

4021. Distinct Points Reachable After Substring Removal

Medium

You are given a string s consisting of characters 'U', 'D', 'L', and 'R', representing moves on an infinite 2D Cartesian grid.

'U': Move from (x, y) to (x, y + 1).
'D': Move from (x, y) to (x, y - 1).
'L': Move from (x, y) to (x - 1, y).
'R': Move from (x, y) to (x + 1, y).

You are also given a positive integer k.

You must choose and remove exactly one contiguous substring of length k from s. Then, start from coordinate (0, 0) and perform the remaining moves in order.

Return an integer denoting the number of distinct final coordinates reachable.

Example 1:

Input: s = "LUL", k = 1

Output: 2

Explanation:

After removing a substring of length 1, s can be "UL", "LL" or "LU". Following these moves, the final coordinates will be (-1, 1), (-2, 0) and (-1, 1) respectively. There are two distinct points (-1, 1) and (-2, 0) so the answer is 2.

Example 2:

Input: s = "UDLR", k = 4

Output: 1

Explanation:

After removing a substring of length 4, s can only be the empty string. The final coordinates will be (0, 0). There is only one distinct point (0, 0) so the answer is 1.

Example 3:

Input: s = "UU", k = 1

Output: 1

Explanation:

After removing a substring of length 1, s becomes "U", which always ends at (0, 1), so there is only one distinct final coordinate.

Constraints:

1 <= s.length <= 10⁵
s consists of only 'U', 'D', 'L', and 'R'.
1 <= k <= s.length

Solution¶

class Solution {
    private int xP[], yP[];
    static class Pair {
        int x, y;
        public Pair(int x, int y) {
            this.x = x;
            this.y = y;
        }
        @Override
        public String toString() {
            return "(" + x + " " + y + ")";
        }
        @Override
        public boolean equals(Object obj) {
            if (this == obj)
                return true;
            if (obj == null || getClass() != obj.getClass())
                return false;
            Pair current = (Pair)(obj);
            return current.x == x && current.y == y;
        }
        @Override
        public int hashCode() {
            return Objects.hash(x, y);
        }
    }
    public int distinctPoints(String s, int k) {
        int n = s.length();

        xP = new int[n];
        yP = new int[n];
        for (int i = 0; i < n; i++) {
            char current = s.charAt(i);
            if (current == 'U') {
                xP[i] = 0;
                yP[i] = 1;
            } else if (current == 'D') {
                xP[i] = 0;
                yP[i] = -1; 
            } else if (current == 'L') {
                xP[i] = -1;
                yP[i] = 0;
            } else if (current == 'R') {
                xP[i] = 1;
                yP[i] = 0;
            }
        }

        for (int i = 1; i < n; i++) {
            xP[i] += xP[i - 1];
            yP[i] += yP[i - 1];
        }

        HashSet<Pair> set = new HashSet<>();
        for (int i = 0; i < n; i++) {
            if (i + k - 1 < n) {
                int l = i, r = i + k - 1;
                int windowSumX = xP[r], windowSumY = yP[r];
                if (l - 1 >= 0) {
                    windowSumX -= xP[l - 1];
                    windowSumY -= yP[l - 1];
                }
                int currX = xP[n - 1] - windowSumX, currY = yP[n - 1] - windowSumY;
                set.add(new Pair(currX, currY));
            }
        }

        return set.size(); 
    }
}

Complexity Analysis¶

Time Complexity: O(?)
Space Complexity: O(?)

Explanation¶

[Add detailed explanation here]