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 <= 105s consists of only 'U', 'D', 'L', and 'R'.1 <= k <= s.lengthProblem Overview: You are given a movement string that changes a point’s position on a 2D grid. After removing exactly one substring, the remaining moves form a new path. The task is to count how many distinct final points can be reached depending on which substring you remove.
Approach 1: Brute Force Simulation (O(n^2) time, O(1) space)
Enumerate every possible substring s[l..r] and simulate the path after removing it. For each pair of indices, build the resulting movement sequence and compute the final coordinate by iterating through the characters. Store each final coordinate in a set to track distinct points. This approach directly models the problem but requires recomputing the path for every removal. With O(n^2) possible substrings and O(n) simulation per case, it quickly becomes impractical for large inputs.
Approach 2: Prefix Sum + Hash Table (O(n) time, O(n) space)
Instead of recomputing positions repeatedly, treat the movement path as coordinate prefix sums. While scanning the string, maintain the position after every step using a prefix array of (x, y) coordinates. Removing substring s[l..r] means the path jumps from prefix l directly to prefix r+1, effectively subtracting the displacement contributed by the removed segment.
The key observation: the final coordinate equals prefix[n] - (prefix[r+1] - prefix[l]). You iterate through possible split points and compute the resulting displacement using prefix differences. A hash table stores each resulting coordinate to count unique endpoints. Because each candidate removal can be evaluated using constant-time arithmetic on prefix coordinates, the entire scan runs in linear time.
This technique relies on path accumulation using prefix sums and efficient uniqueness tracking with hashing. In some implementations, a sliding window-style scan over substring boundaries helps maintain candidate ranges while updating displacement values.
Recommended for interviews: The Prefix Sum + Hash Table approach is what interviewers expect. Starting with brute force shows you understand the effect of removing a substring on the path. Transitioning to prefix coordinates demonstrates algorithmic maturity—reusing precomputed displacement and avoiding repeated simulation. That optimization reduces the complexity from quadratic to linear, which is the key insight behind the optimal solution.
We can use prefix sum arrays to track position changes after each move. Specifically, we use two prefix sum arrays f and g to record the position changes on the x-axis and y-axis respectively after each move.
Initialize f[0] = 0 and g[0] = 0, representing the initial position at (0, 0). Then, we iterate through the string s, and for each character:
g[i] = g[i-1] + 1.g[i] = g[i-1] - 1.f[i] = f[i-1] - 1.f[i] = f[i-1] + 1.Next, we use a hash set to store the distinct final coordinates. For each possible substring removal position i (from k to n), we calculate the final coordinates (a, b) after removing the substring, where a = f[n] - (f[i] - f[i-k]) and b = g[n] - (g[i] - g[i-k]). Add the coordinates (a, b) to the hash set.
Finally, the size of the hash set is the number of distinct final coordinates.
The time complexity is O(n) and the space complexity is O(n), where n is the length of the string s.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Simulation | O(n^2) | O(1) | Useful for understanding the effect of removing each substring or when constraints are very small |
| Prefix Sum + Hash Table | O(n) | O(n) | General case for large strings; computes final coordinates using prefix displacement and tracks distinct results efficiently |
Distinct Points Reachable After Substring Removal | LeetCode 3694 | Biweekly Contest 166 • Sanyam IIT Guwahati • 557 views views
Watch 7 more video solutions →Practice Distinct Points Reachable After Substring Removal with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor