3968. Maximum Manhattan Distance After All Moves

Description

You are given a string moves consisting of the characters 'U', 'D', 'L', 'R', and '_'.

Starting from the origin (0, 0), each character represents one move on a 2D plane:

'U': Move up by 1 unit.
'D': Move down by 1 unit.
'L': Move left by 1 unit.
'R': Move right by 1 unit.
'_': Can be independently replaced with any one of 'U', 'D', 'L', or 'R'.

Return the maximum Manhattan distance from the origin that can be achieved after all moves have been performed.

Example 1:

Input: moves = "L_D_"

Output: 4

Explanation:

One optimal choice is:

'L': (0, 0) -> (-1, 0)
'_' treated as 'D': (-1, 0) -> (-1, -1)
'D': (-1, -1) -> (-1, -2)
'_' treated as 'L': (-1, -2) -> (-2, -2)

The final Manhattan distance from the origin is |0 - (-2)| + |0 - (-2)| = 4.

Example 2:

Input: moves = "U_R"

Output: 3

Explanation:

One optimal choice is:

'U': (0, 0) -> (0, 1)
'_' treated as 'U': (0, 1) -> (0, 2)
'R': (0, 2) -> (1, 2)

The final Manhattan distance from the origin is |0 - 1| + |0 - 2| = 3.

Constraints:

1 <= moves.length <= 10⁵
moves consists of only 'U', 'D', 'L', 'R', and '_'.

Solutions

Solution 1: Greedy

We can use a variable \(x\) to record the vertical distance, a variable \(y\) to record the horizontal distance, and a variable \(z\) to record the number of replaceable moves.

Then the final Manhattan distance is \(|x| + |y| + z\).

The time complexity is \(O(n)\), where \(n\) is the length of the string \(\textit{moves}\). The space complexity is \(O(1)\).

Python3JavaC++GoTypeScript

class Solution:
    def maxDistance(self, moves: str) -> int:
        x = y = z = 0
        for c in moves:
            if c == "U":
                x -= 1
            elif c == "D":
                x += 1
            elif c == "L":
                y -= 1
            elif c == "R":
                y += 1
            else:
                z += 1
        return abs(x) + abs(y) + z

class Solution {
    public int maxDistance(String moves) {
        int x = 0, y = 0, z = 0;
        for (char c : moves.toCharArray()) {
            if (c == 'U') {
                x -= 1;
            } else if (c == 'D') {
                x += 1;
            } else if (c == 'L') {
                y -= 1;
            } else if (c == 'R') {
                y += 1;
            } else {
                z += 1;
            }
        }
        return Math.abs(x) + Math.abs(y) + z;
    }
}

class Solution {
public:
    int maxDistance(string moves) {
        int x = 0, y = 0, z = 0;
        for (char c : moves) {
            if (c == 'U') {
                x -= 1;
            } else if (c == 'D') {
                x += 1;
            } else if (c == 'L') {
                y -= 1;
            } else if (c == 'R') {
                y += 1;
            } else {
                z += 1;
            }
        }
        return abs(x) + abs(y) + z;
    }
};

func maxDistance(moves string) int {
    x, y, z := 0, 0, 0
    for _, c := range moves {
        if c == 'U' {
            x -= 1
        } else if c == 'D' {
            x += 1
        } else if c == 'L' {
            y -= 1
        } else if c == 'R' {
            y += 1
        } else {
            z += 1
        }
    }
    return abs(x) + abs(y) + z
}

func abs(x int) int {
    if x < 0 {
        return -x
    }
    return x
}

function maxDistance(moves: string): number {
    let [x, y, z] = [0, 0, 0];
    for (const c of moves) {
        if (c === 'U') {
            x -= 1;
        } else if (c === 'D') {
            x += 1;
        } else if (c === 'L') {
            y -= 1;
        } else if (c === 'R') {
            y += 1;
        } else {
            z += 1;
        }
    }
    return Math.abs(x) + Math.abs(y) + z;
}

3968. Maximum Manhattan Distance After All Moves

Description

Solutions

Solution 1: Greedy

Comments