Distinct points reachable after substring removal

Hash Table String Sliding Window Prefix Sum

53.8% acceptance

Feb 25, 2026

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

Rust

Time O(n)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn distinct_points(s: String, k: i32) -> i32 {
    let n = s.len();
    let k = k as usize;
    let chars: Vec<char> = s.chars().collect();
    let move_delta = |c: char| -> (i64, i64) {
      match c {
        'U' => (0, 1),
        'D' => (0, -1),
        'L' => (-1, 0),
        'R' => (1, 0),
        _ => (0, 0),
      }
    };
    // Prefix sums
    let mut px = vec![0i64; n + 1];
    let mut py = vec![0i64; n + 1];
    for i in 0..n {
      let (dx, dy) = move_delta(chars[i]);
      px[i + 1] = px[i] + dx;
      py[i + 1] = py[i] + dy;
    }
    // When removing substring [i, i+k-1] (0-indexed), the result is:
    // prefix [0..i] then suffix [i+k..n-1]
    // Final position: (px[i] - px[0]) + (px[n] - px[i+k])
    //                = px[i] + (px[n] - px[i+k])
    // So x = px[i] + px[n] - px[i+k]
    //    y = py[i] + py[n] - py[i+k]
    let total_x = px[n];
    let total_y = py[n];
    let mut positions: std::collections::HashSet<(i64, i64)> = std::collections::HashSet::new();
    for i in 0..=(n - k) {
      let x = px[i] + total_x - px[i + k];
      let y = py[i] + total_y - py[i + k];
      positions.insert((x, y));
    }
    positions.len() as i32
  }
}