3443. Maximum Manhattan Distance After K Changes LeetCode Solution

In this guide, you will get 3443. Maximum Manhattan Distance After K Changes LeetCode Solution with the best time and space complexity. The solution to Maximum Manhattan Distance After K Changes problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.

Table of Contents

1. Problem Statement
2. Complexity Analysis
3. Maximum Manhattan Distance After K Changes solution in C++
4. Maximum Manhattan Distance After K Changes solution in Java
5. Maximum Manhattan Distance After K Changes solution in Python
6. Additional Resources

Problem Statement of Maximum Manhattan Distance After K Changes

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 (xi, yi) and (xj, yj) is |xi – xj| + |yi – yj|.

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 <= 105
0 <= k <= s.length
s consists of only 'N', 'S', 'E', and 'W'.

Complexity Analysis

• Time Complexity: O(4n) = O(n)
• Space Complexity: O(n)

3443. Maximum Manhattan Distance After K Changes LeetCode Solution in C++

class Solution {
 public:
  int maxDistance(string s, int k) {
    return max({flip(s, k, "NE"), flip(s, k, "NW"),  //
                flip(s, k, "SE"), flip(s, k, "SW")});
  }

 private:
  int flip(const string& s, int k, const string& direction) {
    int res = 0;
    int pos = 0;
    int opposite = 0;

    for (const char c : s) {
      if (direction.find(c) != string::npos) {
        ++pos;
      } else {
        --pos;
        ++opposite;
      }
      res = max(res, pos + 2 * min(k, opposite));
    }

    return res;
  }
};
/* code provided by PROGIEZ */

3443. Maximum Manhattan Distance After K Changes LeetCode Solution in Java

class Solution {
  public int maxDistance(String s, int k) {
    return Math.max(Math.max(flip(s, k, "NE"), flip(s, k, "NW")),
                    Math.max(flip(s, k, "SE"), flip(s, k, "SW")));
  }

  private int flip(String s, int k, String direction) {
    int res = 0;
    int pos = 0;
    int opposite = 0;

    for (final char c : s.toCharArray()) {
      if (direction.indexOf(c) >= 0) {
        ++pos;
      } else {
        --pos;
        ++opposite;
      }
      res = Math.max(res, pos + 2 * Math.min(k, opposite));
    }

    return res;
  }
}
// code provided by PROGIEZ

3443. Maximum Manhattan Distance After K Changes LeetCode Solution in Python

class Solution:
  def maxDistance(self, s: str, k: int) -> int:
    return max(self._flip(s, k, 'NE'), self._flip(s, k, 'NW'),
               self._flip(s, k, 'SE'), self._flip(s, k, 'SW'))

  def _flip(self, s: str, k: int, direction: str) -> int:
    res = 0
    pos = 0
    opposite = 0

    for c in s:
      if c in direction:
        pos += 1
      else:
        pos -= 1
        opposite += 1
      res = max(res, pos + 2 * min(k, opposite))

    return res
 # code by PROGIEZ

Additional Resources

• Explore all LeetCode problem solutions at Progiez here
• Explore all problems on LeetCode website here

Happy Coding! Keep following PROGIEZ for more updates and solutions.