#3694
Distinct Points Reachable After Substring Removal
medium · 53.8% accepted · 65 likes · top 45%
hash table · string · sliding window · prefix sum
Description
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.
Solution