3694. Distinct Points Reachable After Substring Removal

MediumHash TableStringPrefix SumSliding Window

LeetCode ↗

Problem Pattern Idea Example Code Complex Pitfalls

Problem Description

You are given a string s made up of the characters 'U', 'D', 'L', and 'R'. Each character represents a single move on an infinite 2D grid:

'U': move up, from (x, y) to (x, y + 1).
'D': move down, from (x, y) to (x, y - 1).
'L': move left, from (x, y) to (x - 1, y).
'R': move right, from (x, y) to (x + 1, y).

You are also given a positive integer k.

Before performing any moves, you must remove exactly one contiguous substring of length k from s. After the removal, you start at the origin (0, 0) and execute all of the remaining moves in their original order.

Since the substring of length k can be removed from different positions in s, different removals may lead to different ending positions. Your task is to count how many distinct final coordinates can be reached, considering every possible choice of the removed substring.

For example, if s = "LUL" and k = 1, removing each of the three characters leaves the move sequences "UL", "LL", and "LU". These end at (-1, 1), (-2, 0), and (-1, 1) respectively, giving 2 distinct final coordinates.

Return a single integer — the number of distinct final coordinates reachable.

Quick Interview Experience

Help others by sharing your interview experience

Have you seen this problem before?

How We Pick the Algorithm

Why Prefix Sums?

This problem maps to Prefix Sums through a short path in the full flowchart.

The final coordinate after removing a window is just the total displacement minus the window's displacement, which prefix sums compute in O(1) per window.

Open in Flowchart

Intuition

The first key observation is that the moves are simply displacement vectors, and the final position is just the sum of all individual move vectors. The order of moves does not affect where you end up — only which moves you perform matters.

This means removing a substring of length k is equivalent to subtracting the total displacement of that substring from the total displacement of the whole string. If the full string ends at position (X, Y) and the removed window contributes a displacement of (dx, dy), then the final position after removal is simply (X - dx, Y - dy).

So instead of simulating the remaining moves for every possible removal — which would cost O(n) per removal and O(n²) overall — we only need a fast way to compute the displacement of any length-k window.

This is exactly the kind of "range sum" query that prefix sums solve. If we precompute prefix sums f[i] and g[i] representing the x- and y-displacement after the first i moves, then the displacement of the window ending at index i is:

dx = f[i] - f[i - k]
dy = g[i] - g[i - k]

Each window's resulting final coordinate can then be computed in O(1) time as (f[n] - dx, g[n] - dy).

Finally, since different windows may produce the same final coordinate, we collect all results in a hash set to automatically deduplicate them, and the answer is the size of the set. The total time complexity drops to O(n).

Pattern Learn more about Prefix Sum and Sliding Window patterns.

Solution Approach

The implementation follows the Prefix Sum + Hash Table pattern and consists of two main phases: building the prefix sums, and enumerating all possible removal windows.

Step 1: Build Prefix Sum Arrays

We create two arrays f and g of size n + 1, where:

f[i] stores the net x-displacement after performing the first i moves.
g[i] stores the net y-displacement after performing the first i moves.

Both start with f[0] = 0 and g[0] = 0, representing the origin (0, 0). We then scan the string once, maintaining running coordinates x and y, updating them based on each character:

'U': y += 1
'D': y -= 1
'L': x -= 1
'R': x += 1

After processing the i-th character, we record f[i] = x and g[i] = y.

f = [0] * (n + 1)
g = [0] * (n + 1)
x = y = 0
for i, c in enumerate(s, 1):
    if c == "U":
        y += 1
    elif c == "D":
        y -= 1
    elif c == "L":
        x -= 1
    else:
        x += 1
    f[i] = x
    g[i] = y

Note that f[n] and g[n] give the final position (X, Y) if no moves were removed.

Step 2: Enumerate All Removal Windows

A removed substring of length k ending at index i (1-indexed) covers the moves from position i - k + 1 to i. Its displacement is obtained by a standard prefix sum difference:

x-displacement of the window: f[i] - f[i - k]
y-displacement of the window: g[i] - g[i - k]

Subtracting this from the total displacement gives the final coordinate after removal:

a = f[n] - (f[i] - f[i - k])
b = g[n] - (g[i] - g[i - k])

We slide i from k to n, covering every valid window exactly once, and insert each resulting coordinate (a, b) into a hash set. The set handles deduplication automatically — windows with identical displacements produce the same coordinate and are counted only once.

st = set()
for i in range(k, n + 1):
    a = f[n] - (f[i] - f[i - k])
    b = g[n] - (g[i] - g[i - k])
    st.add((a, b))
return len(st)

Step 3: Return the Answer

The number of distinct final coordinates is simply the size of the hash set, len(st).

Complexity Analysis

Time complexity: O(n) — one pass to build the prefix sums and one pass over all n - k + 1 windows, each evaluated in O(1).
Space complexity: O(n) — for the two prefix sum arrays and the hash set, which holds at most n - k + 1 coordinates.

Example Walkthrough

Let's trace through the algorithm with s = "LULL" and k = 2, so n = 4.

Step 1: Build the prefix sum arrays

Starting from (0, 0), we process each character and record the running x- and y-displacements:

`i`	Move	`x` after move	`y` after move	`f[i]`	`g[i]`
0	—	0	0	0	0
1	`'L'`	-1	0	-1	0
2	`'U'`	-1	1	-1	1
3	`'L'`	-2	1	-2	1
4	`'L'`	-3	1	-3	1

So f = [0, -1, -1, -2, -3] and g = [0, 0, 1, 1, 1]. The full string (with nothing removed) would end at (f[4], g[4]) = (-3, 1).

Step 2: Enumerate every length-2 removal window

We slide i from k = 2 to n = 4. For each window we compute its displacement via prefix sum differences, then subtract it from the total:

i = 2 — window is s[1..2] = "LU":
- dx = f[2] - f[0] = -1 - 0 = -1, dy = g[2] - g[0] = 1 - 0 = 1
- Final coordinate: (-3 - (-1), 1 - 1) = (-2, 0) → set becomes {(-2, 0)}
i = 3 — window is s[2..3] = "UL":
- dx = f[3] - f[1] = -2 - (-1) = -1, dy = g[3] - g[1] = 1 - 0 = 1
- Final coordinate: (-3 - (-1), 1 - 1) = (-2, 0) → duplicate, set stays {(-2, 0)}
i = 4 — window is s[3..4] = "LL":
- dx = f[4] - f[2] = -3 - (-1) = -2, dy = g[4] - g[2] = 1 - 1 = 0
- Final coordinate: (-3 - (-2), 1 - 0) = (-1, 1) → set becomes {(-2, 0), (-1, 1)}

Notice how the windows "LU" and "UL" have the same displacement (-1, 1) even though the moves are in different orders — the hash set deduplicates them automatically.

Step 3: Return the answer

The set contains 2 coordinates, so the answer is len(st) = 2.

Sanity check by direct simulation: removing "LU" leaves "LL" → (-2, 0); removing "UL" leaves "LL" → (-2, 0); removing the last "LL" leaves "LU" → (-1, 1). The distinct endpoints are (-2, 0) and (-1, 1) — exactly 2, matching our result.

Solution Implementation

1class Solution:
2    def distinctPoints(self, s: str, k: int) -> int:
3        n = len(s)
4        # prefix_x[i] and prefix_y[i] store the x and y coordinates
5        # after performing the first i moves (prefix sums of displacement)
6        prefix_x = [0] * (n + 1)
7        prefix_y = [0] * (n + 1)
8        x = y = 0
9        for i, move in enumerate(s, 1):
10            # Update the current position according to the move direction
11            if move == "U":
12                y += 1
13            elif move == "D":
14                y -= 1
15            elif move == "L":
16                x -= 1
17            else:  # move == "R"
18                x += 1
19            prefix_x[i] = x
20            prefix_y[i] = y
21
22        # Use a set to collect all distinct final positions
23        distinct_positions = set()
24        # Enumerate every window of length k to be removed:
25        # the window covers moves (i - k + 1) .. i (1-indexed)
26        for i in range(k, n + 1):
27            # The final position equals the total displacement
28            # minus the displacement contributed by the removed window
29            final_x = prefix_x[n] - (prefix_x[i] - prefix_x[i - k])
30            final_y = prefix_y[n] - (prefix_y[i] - prefix_y[i - k])
31            distinct_positions.add((final_x, final_y))
32
33        # The answer is the number of distinct final positions
34        return len(distinct_positions)
35

1import java.util.HashSet;
2import java.util.Set;
3
4class Solution {
5    public int distinctPoints(String s, int k) {
6        int n = s.length();
7
8        // prefixX[i] / prefixY[i] store the x / y coordinate
9        // after performing the first i moves of s.
10        int[] prefixX = new int[n + 1];
11        int[] prefixY = new int[n + 1];
12
13        int x = 0, y = 0;
14        for (int i = 1; i <= n; ++i) {
15            char move = s.charAt(i - 1);
16            if (move == 'U') {
17                ++y;
18            } else if (move == 'D') {
19                --y;
20            } else if (move == 'L') {
21                --x;
22            } else { // move == 'R'
23                ++x;
24            }
25            prefixX[i] = x;
26            prefixY[i] = y;
27        }
28
29        // Removing a window of k moves [i - k + 1, i] means the final
30        // position is the total displacement minus the displacement
31        // contributed by that window.
32        Set<Long> distinctEndpoints = new HashSet<>();
33        for (int i = k; i <= n; ++i) {
34            // Final x after deleting the window of length k ending at i
35            int finalX = prefixX[n] - (prefixX[i] - prefixX[i - k]);
36            // Final y after deleting the same window
37            int finalY = prefixY[n] - (prefixY[i] - prefixY[i - k]);
38
39            // Encode the 2D point (finalX, finalY) into a single long.
40            // Coordinates are bounded by n in absolute value, so using a
41            // base of (2n + 1) guarantees a collision-free encoding.
42            long encoded = (long) finalX * (2L * n + 1) + finalY;
43            distinctEndpoints.add(encoded);
44        }
45
46        return distinctEndpoints.size();
47    }
48}
49

1class Solution {
2public:
3    int distinctPoints(string s, int k) {
4        int n = s.size();
5
6        // prefixX[i] / prefixY[i]: coordinates after executing the first i moves
7        vector<int> prefixX(n + 1), prefixY(n + 1);
8
9        int curX = 0, curY = 0;
10        for (int i = 1; i <= n; ++i) {
11            char move = s[i - 1];
12            if (move == 'U')
13                ++curY;
14            else if (move == 'D')
15                --curY;
16            else if (move == 'L')
17                --curX;
18            else // move == 'R'
19                ++curX;
20            prefixX[i] = curX;
21            prefixY[i] = curY;
22        }
23
24        // Set of distinct final positions, each encoded as a single 64-bit key
25        unordered_set<long long> pointSet;
26
27        // Removing the substring s[i-k..i-1] (1-indexed window ending at i)
28        // means the net displacement of that window is subtracted from the
29        // total displacement of the whole string.
30        for (int i = k; i <= n; ++i) {
31            int finalX = prefixX[n] - (prefixX[i] - prefixX[i - k]);
32            int finalY = prefixY[n] - (prefixY[i] - prefixY[i - k]);
33
34            // Coordinates lie in [-n, n], so use a base of (2n + 1)
35            // to encode (finalX, finalY) without collisions.
36            pointSet.insert(1LL * finalX * (2 * n + 1) + finalY);
37        }
38
39        return pointSet.size();
40    }
41};
42

1/**
2 * Counts the number of distinct end points reachable after removing
3 * exactly one contiguous substring of length k from the movement string.
4 *
5 * @param s - The movement string consisting of 'U', 'D', 'L', 'R'
6 * @param k - The length of the contiguous substring to remove
7 * @returns The number of distinct final points
8 */
9function distinctPoints(s: string, k: number): number {
10    const n: number = s.length;
11
12    // prefixX[i] / prefixY[i]: x / y coordinate after performing the first i moves
13    const prefixX: number[] = new Array(n + 1).fill(0);
14    const prefixY: number[] = new Array(n + 1).fill(0);
15
16    // Current coordinates while scanning the moves
17    let x: number = 0;
18    let y: number = 0;
19
20    // Build the prefix-sum arrays of coordinates
21    for (let i = 1; i <= n; ++i) {
22        const move: string = s[i - 1];
23        if (move === 'U') {
24            ++y; // Move up
25        } else if (move === 'D') {
26            --y; // Move down
27        } else if (move === 'L') {
28            --x; // Move left
29        } else {
30            ++x; // Move right
31        }
32        prefixX[i] = x;
33        prefixY[i] = y;
34    }
35
36    // Set used to store the distinct end points (encoded as a single number)
37    const points: Set<number> = new Set<number>();
38
39    // Enumerate every window [i - k + 1, i] of length k to be removed
40    for (let i = k; i <= n; ++i) {
41        // Final x coordinate = total displacement minus the removed window's displacement
42        const endX: number = prefixX[n] - (prefixX[i] - prefixX[i - k]);
43        // Final y coordinate = total displacement minus the removed window's displacement
44        const endY: number = prefixY[n] - (prefixY[i] - prefixY[i - k]);
45        // Encode the point (endX, endY) into a unique number and store it
46        points.add(endX * n + endY);
47    }
48
49    // The size of the set is the number of distinct end points
50    return points.size;
51}
52

Time and Space Complexity

Time Complexity: O(n), where n is the length of the string s.
- The first loop iterates over all n characters of s once, computing the running coordinates and filling the prefix arrays f and g. Each iteration performs constant-time work, so this step costs O(n).
- The second loop runs over indices from k to n, which is at most n - k + 1 iterations. Each iteration computes the pair (a, b) in O(1) and inserts it into the hash set in average O(1) time, so this step also costs O(n).
- Overall, the total time is O(n) + O(n) = O(n).
Space Complexity: O(n), where n is the length of the string s.
- The prefix sum arrays f and g each take O(n + 1) = O(n) space.
- The set st stores at most n - k + 1 distinct points, contributing another O(n) in the worst case.
- Therefore, the total space used is O(n).

Pattern Learn more about how to find time and space complexity quickly.

Common Pitfalls

Pitfall: Off-by-One Errors in the Window Enumeration Range

A frequent mistake is writing the removal-window loop with incorrect bounds, such as:

# WRONG: misses the last window ending at index n
for i in range(k, n):
    a = prefix_x[n] - (prefix_x[i] - prefix_x[i - k])
    b = prefix_y[n] - (prefix_y[i] - prefix_y[i - k])
    distinct_positions.add((a, b))

or mixing up 0-indexed and 1-indexed conventions:

# WRONG: i - k can become -1, silently indexing from the end of the array
for i in range(n):
    a = prefix_x[n] - (prefix_x[i + k] - prefix_x[i - 1])  # i - 1 == -1 when i == 0
    ...

Why it happens: The prefix sum arrays use the convention that prefix_x[i] is the position after the first i moves, so they have size n + 1 and the valid window-end positions run from k through n inclusive. Two distinct mistakes arise from mishandling this:

Missing the final window. Using range(k, n) instead of range(k, n + 1) skips the window that removes the last k characters of s. The code still runs without errors and may even pass small tests, but it can undercount distinct coordinates whenever the last window produces a unique final position. For example, with s = "LUL" and k = 1, the loop must consider i = 1, 2, 3; stopping at i = 2 never evaluates removing the trailing 'L'.
Negative index silently wrapping. When translating to 0-indexed logic, an expression like prefix_x[i - 1] with i = 0 evaluates prefix_x[-1], which in Python is the last element of the array rather than an error. This produces wildly incorrect displacements with no exception raised, making the bug hard to detect — the program appears healthy but returns wrong answers.

Solution: Stick consistently to the 1-indexed prefix-sum convention and derive the loop bounds from first principles: a window of length k ending at position i requires i - k >= 0 and i <= n, so the loop is exactly range(k, n + 1):

for i in range(k, n + 1):
    final_x = prefix_x[n] - (prefix_x[i] - prefix_x[i - k])
    final_y = prefix_y[n] - (prefix_y[i] - prefix_y[i - k])
    distinct_positions.add((final_x, final_y))

A quick sanity check helps confirm correctness: the loop should execute exactly n - k + 1 times — one iteration per possible removal position. Verifying len(range(k, n + 1)) == n - k + 1 against a hand-computed small case (such as the s = "LUL", k = 1 example, which has 3 windows) catches both bound errors immediately.

Ready to land your dream job?

Unlock your dream job with a 5-minute quiz for a personalized study roadmap!

Get My Roadmap

Discover Your Strengths and Weaknesses: Take Our 5-Minute Quiz to Get a Personalized Study Roadmap:

Which of the following is a good use case for backtracking?

Combinatorial problems

Random number generation

Topological sorting

Matrix multiplication

I don't know