Distinct Points Reachable After Substring Removal - Video Solutions
Distinct Points Reachable After Substring Removal | LeetCode 3694 | Biweekly Contest 166
Distinct Points Reachable After Substring Removal - Video Solution
Watch 7 video solutions for Distinct Points Reachable After Substring Removal, a medium level problem involving Hash Table, String, Sliding Window. This walkthrough by Sanyam IIT Guwahati has 576 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
Problem Statement
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 <= 105sconsists of only'U','D','L', and'R'.1 <= k <= s.length
Approach Overview
Problem 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.
Complexity Analysis
| 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 |