Tap here to switch tabs
Problem
Submissions

Problem: Distinct Points Reachable After Substring Removal

Distinct Points Reachable After Substring Removal gives a move string and a substring length. Remove one contiguous substring of that length, then return the number of distinct final coordinates.

Statement

You are given a string s representing a sequence of moves on a 2D2 {D} Cartesian plane and an integer k. A person starts at coordinate (0,0)(0, 0).

Each character in s represents a movement:

  • 'U' moves 11 unit up to (x,y+1)(x, y + 1)

  • 'D' moves 11 unit down to (x,y−1)(x, y - 1)

  • 'L' moves 11 unit left to (x−1,y)(x - 1, y)

  • 'R' moves 11 unit right to (x+1,y)(x + 1, y)

You must remove exactly one contiguous substring of length k from s. After the substring is removed, the remaining characters are concatenated in their original order, and the person executes the resulting sequence of moves starting from (0,0)(0, 0).

Return the number of distinct final coordinates reachable.

Constraints:

  • 1≤1 \leq s.length ≤105\leq 10^5

  • s consists only of 'U', 'D', 'L', and 'R'

  • 1≤1 \leq k ≤\leq s.length

⋮
Tap here to switch tabs
Problem
Submissions

Problem: Distinct Points Reachable After Substring Removal

Distinct Points Reachable After Substring Removal gives a move string and a substring length. Remove one contiguous substring of that length, then return the number of distinct final coordinates.

Statement

You are given a string s representing a sequence of moves on a 2D2 {D} Cartesian plane and an integer k. A person starts at coordinate (0,0)(0, 0).

Each character in s represents a movement:

  • 'U' moves 11 unit up to (x,y+1)(x, y + 1)

  • 'D' moves 11 unit down to (x,y−1)(x, y - 1)

  • 'L' moves 11 unit left to (x−1,y)(x - 1, y)

  • 'R' moves 11 unit right to (x+1,y)(x + 1, y)

You must remove exactly one contiguous substring of length k from s. After the substring is removed, the remaining characters are concatenated in their original order, and the person executes the resulting sequence of moves starting from (0,0)(0, 0).

Return the number of distinct final coordinates reachable.

Constraints:

  • 1≤1 \leq s.length ≤105\leq 10^5

  • s consists only of 'U', 'D', 'L', and 'R'

  • 1≤1 \leq k ≤\leq s.length