3443. Maximum Manhattan Distance After K Changes

Description

You are given a string s consisting of the characters 'N', 'S', 'E', and 'W', where s[i] indicates movements in an infinite grid:

'N' : Move north by 1 unit.
'S' : Move south by 1 unit.
'E' : Move east by 1 unit.
'W' : Move west by 1 unit.

Initially, you are at the origin (0, 0). You can change at most k characters to any of the four directions.

Find the maximum Manhattan distance from the origin that can be achieved at any time while performing the movements in order.

The Manhattan Distance between two cells (x_i, y_i) and (x_j, y_j) is |x_i - x_j| + |y_i - y_j|.

Example 1:

Input: s = "NWSE", k = 1

Output: 3

Explanation:

Change s[2] from 'S' to 'N'. The string s becomes "NWNE".

Movement	Position (x, y)	Manhattan Distance	Maximum
s[0] == 'N'	(0, 1)	0 + 1 = 1	1
s[1] == 'W'	(-1, 1)	1 + 1 = 2	2
s[2] == 'N'	(-1, 2)	1 + 2 = 3	3
s[3] == 'E'	(0, 2)	0 + 2 = 2	3

The maximum Manhattan distance from the origin that can be achieved is 3. Hence, 3 is the output.

Example 2:

Input: s = "NSWWEW", k = 3

Output: 6

Explanation:

Change s[1] from 'S' to 'N', and s[4] from 'E' to 'W'. The string s becomes "NNWWWW".

The maximum Manhattan distance from the origin that can be achieved is 6. Hence, 6 is the output.

Constraints:

1 <= s.length <= 10⁵
0 <= k <= s.length
s consists of only 'N', 'S', 'E', and 'W'.

Solutions

Solution 1: Enumeration + Greedy

We can enumerate four cases: \(\textit{SE}\), \(\textit{SW}\), \(\textit{NE}\), and \(\textit{NW}\), and then calculate the maximum Manhattan distance for each case.

We define a function \(\text{calc}(a, b)\) to calculate the maximum Manhattan distance when the effective directions are \(\textit{a}\) and \(\textit{b}\).

We define a variable \(\textit{mx}\) to record the current Manhattan distance, a variable \(\textit{cnt}\) to record the number of changes made, and initialize the answer \(\textit{ans}\) to \(0\).

Traverse the string \(\textit{s}\). If the current character is \(\textit{a}\) or \(\textit{b}\), increment \(\textit{mx}\) by \(1\). Otherwise, if \(\textit{cnt} < k\), increment \(\textit{mx}\) by \(1\) and increment \(\textit{cnt}\) by \(1\). Otherwise, decrement \(\textit{mx}\) by \(1\). Then update \(\textit{ans} = \max(\textit{ans}, \textit{mx})\).

Finally, return the maximum value among the four cases.

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

Python3JavaC++GoTypeScript

class Solution:
    def maxDistance(self, s: str, k: int) -> int:
        def calc(a: str, b: str) -> int:
            ans = mx = cnt = 0
            for c in s:
                if c == a or c == b:
                    mx += 1
                elif cnt < k:
                    cnt += 1
                    mx += 1
                else:
                    mx -= 1
                ans = max(ans, mx)
            return ans

        a = calc("S", "E")
        b = calc("S", "W")
        c = calc("N", "E")
        d = calc("N", "W")
        return max(a, b, c, d)

class Solution {
    private char[] s;
    private int k;

    public int maxDistance(String s, int k) {
        this.s = s.toCharArray();
        this.k = k;
        int a = calc('S', 'E');
        int b = calc('S', 'W');
        int c = calc('N', 'E');
        int d = calc('N', 'W');
        return Math.max(Math.max(a, b), Math.max(c, d));
    }

    private int calc(char a, char b) {
        int ans = 0, mx = 0, cnt = 0;
        for (char c : s) {
            if (c == a || c == b) {
                ++mx;
            } else if (cnt < k) {
                ++mx;
                ++cnt;
            } else {
                --mx;
            }
            ans = Math.max(ans, mx);
        }
        return ans;
    }
}

class Solution {
public:
    int maxDistance(string s, int k) {
        auto calc = [&](char a, char b) {
            int ans = 0, mx = 0, cnt = 0;
            for (char c : s) {
                if (c == a || c == b) {
                    ++mx;
                } else if (cnt < k) {
                    ++mx;
                    ++cnt;
                } else {
                    --mx;
                }
                ans = max(ans, mx);
            }
            return ans;
        };
        int a = calc('S', 'E');
        int b = calc('S', 'W');
        int c = calc('N', 'E');
        int d = calc('N', 'W');
        return max({a, b, c, d});
    }
};

func maxDistance(s string, k int) int {
    calc := func(a rune, b rune) int {
        var ans, mx, cnt int
        for _, c := range s {
            if c == a || c == b {
                mx++
            } else if cnt < k {
                mx++
                cnt++
            } else {
                mx--
            }
            ans = max(ans, mx)
        }
        return ans
    }
    a := calc('S', 'E')
    b := calc('S', 'W')
    c := calc('N', 'E')
    d := calc('N', 'W')
    return max(a, b, c, d)
}

function maxDistance(s: string, k: number): number {
    const calc = (a: string, b: string): number => {
        let [ans, mx, cnt] = [0, 0, 0];
        for (const c of s) {
            if (c === a || c === b) {
                ++mx;
            } else if (cnt < k) {
                ++mx;
                ++cnt;
            } else {
                --mx;
            }
            ans = Math.max(ans, mx);
        }
        return ans;
    };
    const a = calc('S', 'E');
    const b = calc('S', 'W');
    const c = calc('N', 'E');
    const d = calc('N', 'W');
    return Math.max(a, b, c, d);
}

3443. Maximum Manhattan Distance After K Changes

Description

Solutions

Solution 1: Enumeration + Greedy

Comments