LeetCode 3694 - Distinct Points Reachable After Substring Removal

We are given a movement string s consisting of the four directions: - U increases the y-coordinate by 1. - D decreases the y-coordinate by 1. - L decreases the x-coordinate by 1. - R increases the x-coordinate by 1.

leetcodemediumhash-tablestringsliding-windowprefix-sum

LeetCode Problem 3694

Difficulty: 🟡 Medium
Topics: Hash Table, String, Sliding Window, Prefix Sum

Solution

LeetCode 3694 - Distinct Points Reachable After Substring Removal

Problem Understanding

We are given a movement string s consisting of the four directions:

  • U increases the y-coordinate by 1.
  • D decreases the y-coordinate by 1.
  • L decreases the x-coordinate by 1.
  • R increases the x-coordinate by 1.

Starting from (0, 0), the entire string represents a walk on an infinite 2D grid.

The twist is that we must remove exactly one contiguous substring of length k. After removing that substring, the remaining characters are concatenated together, and we execute the resulting movement sequence from (0, 0).

For every possible substring of length k, we obtain a final coordinate. Some different removals may lead to the same final coordinate. The goal is to count how many distinct final coordinates can be produced.

The input consists of:

  • A string s of length n.
  • An integer k.

The output is a single integer representing the number of unique ending coordinates achievable after removing exactly one contiguous substring of length k.

The constraints are important:

  • n can be as large as 100000.
  • There are n - k + 1 possible substrings to remove.

Since n is large, any solution that recomputes the resulting path from scratch for every removal will be too slow. We need an approach that processes each removal in constant time after some preprocessing.

Some important edge cases are:

  • k = n, where the entire string is removed and the answer is always 1.
  • Multiple removals producing the same coordinate.
  • Strings containing only one direction.
  • Very large inputs where an O(n²) solution would time out.

Approaches

Brute Force

A straightforward solution is to try every possible substring of length k.

For each starting position i:

  1. Remove s[i:i+k].
  2. Construct the remaining string.
  3. Simulate all moves from (0, 0).
  4. Store the final coordinate in a set.

The set size at the end is the answer.

This approach is correct because it directly evaluates every valid removal and records the resulting endpoint.

However, there are O(n) possible removals, and each simulation takes O(n) time. Therefore the total complexity is O(n²), which is far too slow for n = 100000.

Optimal Observation

Instead of recomputing the walk each time, observe what happens to the final displacement.

Let:

  • total = (Tx, Ty) be the displacement of the entire string.
  • removed = (Rx, Ry) be the displacement contributed by the removed substring.

After removing that substring, the remaining path contributes:

total - removed

The order of moves no longer matters when considering only the final coordinate. The final position depends solely on the net displacement of the remaining moves.

Therefore, for every removable window of length k, we only need the displacement of that window.

If we can compute each window displacement in O(1) time using prefix sums, then every possible final coordinate can be generated in O(1) time and inserted into a hash set.

This reduces the total complexity to O(n).

Approach Comparison

Approach Time Complexity Space Complexity Notes
Brute Force O(n²) O(n) Rebuilds and simulates the path for every removal
Optimal O(n) O(n) Uses prefix sums to compute each removed displacement in constant time

Algorithm Walkthrough

  1. Let n = len(s).
  2. Build prefix displacement arrays for x and y coordinates.

Define:

  • prefixX[i] = net x displacement after processing the first i characters.
  • prefixY[i] = net y displacement after processing the first i characters.

The arrays have length n + 1, with index 0 initialized to zero. 3. Process the string once and fill the prefix arrays.

For each character:

  • U contributes (0, 1)
  • D contributes (0, -1)
  • L contributes (-1, 0)
  • R contributes (1, 0)
  1. The total displacement of the original string is:
totalX = prefixX[n]
totalY = prefixY[n]
  1. Create a hash set that will store resulting coordinates.
  2. Iterate through every possible removal window.

The starting index start ranges from:

0 ... n-k
  1. For each window [start, start+k-1], compute its displacement using prefix sums:
removedX = prefixX[start+k] - prefixX[start]
removedY = prefixY[start+k] - prefixY[start]
  1. Compute the final coordinate after removing that window:
finalX = totalX - removedX
finalY = totalY - removedY
  1. Insert (finalX, finalY) into the hash set.
  2. After processing all windows, return the size of the hash set.

Why it works

The final coordinate of any movement sequence equals the sum of all move vectors. Removing a substring simply subtracts that substring's displacement from the total displacement of the original string. Prefix sums allow us to obtain every substring displacement in constant time. Since every valid removal is considered exactly once and every resulting coordinate is inserted into a set, the set size is precisely the number of distinct reachable final coordinates.

Python Solution

class Solution:
    def distinctPoints(self, s: str, k: int) -> int:
        n = len(s)

        prefix_x = [0] * (n + 1)
        prefix_y = [0] * (n + 1)

        for i, ch in enumerate(s):
            prefix_x[i + 1] = prefix_x[i]
            prefix_y[i + 1] = prefix_y[i]

            if ch == 'U':
                prefix_y[i + 1] += 1
            elif ch == 'D':
                prefix_y[i + 1] -= 1
            elif ch == 'L':
                prefix_x[i + 1] -= 1
            else:  # 'R'
                prefix_x[i + 1] += 1

        total_x = prefix_x[n]
        total_y = prefix_y[n]

        reachable = set()

        for start in range(n - k + 1):
            removed_x = prefix_x[start + k] - prefix_x[start]
            removed_y = prefix_y[start + k] - prefix_y[start]

            final_x = total_x - removed_x
            final_y = total_y - removed_y

            reachable.add((final_x, final_y))

        return len(reachable)

The implementation begins by constructing prefix sums for the x and y displacements separately. Each position stores the net movement contributed by all characters before that index.

After preprocessing, the total displacement of the original path is immediately available from the last prefix entries.

For every possible removal window, the displacement of the removed substring is obtained using a standard prefix sum difference. Subtracting that displacement from the total displacement yields the endpoint after removal.

The resulting coordinate is inserted into a set, which automatically removes duplicates. Finally, the size of the set is returned.

Go Solution

func distinctPoints(s string, k int) int {
	n := len(s)

	prefixX := make([]int, n+1)
	prefixY := make([]int, n+1)

	for i := 0; i < n; i++ {
		prefixX[i+1] = prefixX[i]
		prefixY[i+1] = prefixY[i]

		switch s[i] {
		case 'U':
			prefixY[i+1]++
		case 'D':
			prefixY[i+1]--
		case 'L':
			prefixX[i+1]--
		case 'R':
			prefixX[i+1]++
		}
	}

	totalX := prefixX[n]
	totalY := prefixY[n]

	type Point struct {
		x int
		y int
	}

	reachable := make(map[Point]struct{})

	for start := 0; start <= n-k; start++ {
		removedX := prefixX[start+k] - prefixX[start]
		removedY := prefixY[start+k] - prefixY[start]

		finalX := totalX - removedX
		finalY := totalY - removedY

		reachable[Point{finalX, finalY}] = struct{}{}
	}

	return len(reachable)
}

The Go implementation follows the same logic as the Python version. Since Go does not have a built in tuple type, a small Point struct is used as the key in the hash map. The map value is an empty struct because only key existence matters. Integer overflow is not a concern because coordinates can never exceed ±100000.

Worked Examples

Example 1

Input

s = "LUL"
k = 1

Prefix Arrays

i Character prefixX prefixY
0 Start 0 0
1 L -1 0
2 U -1 1
3 L -2 1

Total displacement:

(-2, 1)

Window Analysis

Removed Window Removed Displacement Final Coordinate
"L" at index 0 (-1, 0) (-1, 1)
"U" at index 1 (0, 1) (-2, 0)
"L" at index 2 (-1, 0) (-1, 1)

Distinct coordinates:

(-1, 1)
(-2, 0)

Answer:

2

Example 2

Input

s = "UDLR"
k = 4

Total displacement:

(0, 0)

Only one removable window exists:

Removed Window Removed Displacement Final Coordinate
"UDLR" (0, 0) (0, 0)

Distinct coordinates:

{(0, 0)}

Answer:

1

Example 3

Input

s = "UU"
k = 1

Prefix Arrays

i Character prefixX prefixY
0 Start 0 0
1 U 0 1
2 U 0 2

Total displacement:

(0, 2)

Window Analysis

Removed Window Removed Displacement Final Coordinate
First U (0, 1) (0, 1)
Second U (0, 1) (0, 1)

Only one unique coordinate exists.

Answer:

1

Complexity Analysis

Measure Complexity Explanation
Time O(n) One pass to build prefix sums and one pass over all removable windows
Space O(n) Prefix arrays plus the set of distinct coordinates

The prefix arrays require O(n) space. Each possible removal window is processed exactly once in constant time. Therefore the overall running time is linear in the length of the string.

Test Cases

sol = Solution()

assert sol.distinctPoints("LUL", 1) == 2      # Example 1
assert sol.distinctPoints("UDLR", 4) == 1     # Example 2
assert sol.distinctPoints("UU", 1) == 1       # Example 3

assert sol.distinctPoints("U", 1) == 1        # Single character, remove all
assert sol.distinctPoints("LLLL", 1) == 1     # Every removal gives same endpoint
assert sol.distinctPoints("LRLR", 2) == 3     # Multiple distinct results

assert sol.distinctPoints("RRRRR", 5) == 1    # Entire string removed
assert sol.distinctPoints("UDUDUD", 1) == 2   # Repeated canceling pattern
assert sol.distinctPoints("URDL", 1) == 4     # Every direction contributes differently

assert sol.distinctPoints("R", 1) == 1        # Minimum size input
assert sol.distinctPoints("ULDRULDR", 3) >= 1 # General mixed case

Test Summary

Test Why
"LUL", 1 Validates the first example
"UDLR", 4 Entire string removed
"UU", 1 Duplicate results from different removals
"U", 1 Smallest possible input
"LLLL", 1 All removals produce identical coordinates
"LRLR", 2 Multiple unique endpoints
"RRRRR", 5 Boundary case where k = n
"UDUDUD", 1 Alternating movements with repeated effects
"URDL", 1 Different windows create different displacements
"ULDRULDR", 3 General mixed movement pattern

Edge Cases

Removing the Entire String

When k = n, there is exactly one removable substring, the entire string itself. After removal, no moves remain, so the final coordinate is always (0, 0). The implementation naturally handles this because there is only one window and its displacement equals the total displacement.

Multiple Windows Producing the Same Coordinate

Different substrings can have identical net displacement. When this happens, removing either substring produces the same final coordinate. A common bug is counting removals rather than distinct coordinates. Using a hash set guarantees duplicates are merged automatically.

Repeated Single Direction Strings

Consider a string such as "UUUUU" with k = 2. Every removable substring has displacement (0, 2), so every removal leads to exactly the same endpoint. The algorithm correctly computes the same coordinate for every window and the set ends up containing only one entry.

Very Large Inputs

With n = 100000, an O(n²) simulation would require billions of operations. The prefix sum approach computes each window displacement in constant time, keeping the total work linear and ensuring the solution remains efficient within the problem constraints.