Maximum Manhattan Distance After K Changes | Leetcode

In this problem, you are given a string s consisting of the characters 'N', 'S', 'E', and 'W', which represent movements on an infinite grid. The goal is to find the maximum Manhattan distance from the origin (0, 0) after making at most k changes in the directions of the moves. The Manhattan distance between two points (x1, y1) and (x2, y2) is defined as |x1 - x2| + |y1 - y2|.

Let's break down how we can solve this problem step by step and look at the approach, time complexity, and space complexity.

---

Problem with an Example:

Let's go through an example to understand the problem.

Example 1: Input: s = "NWSE", k = 1

• Initially, we are at the origin (0, 0).
• We can move north by 1 unit ('N'), south by 1 unit ('S'), east by 1 unit ('E'), and west by 1 unit ('W').

The goal is to maximize the Manhattan distance, which is the sum of the absolute values of the x and y coordinates, by changing at most k characters.

Step-by-Step Explanation:

1. Starting at (0, 0):
   • Move 'N': New position is (0, 1) → Manhattan distance = 1
   • Move 'W': New position is (-1, 1) → Manhattan distance = 2
   • Move 'S': New position is (-1, 0) → Manhattan distance = 1
   • Move 'E': New position is (0, 0) → Manhattan distance = 0

Now, we can make one change (k = 1). A good strategy is to change 'S' to 'N' to maximize the distance.

• After changing 'S' to 'N', the string becomes "NWNE", and the movements will be:
  • Move 'N': Position (0, 1) → Manhattan distance = 1
  • Move 'W': Position (-1, 1) → Manhattan distance = 2
  • Move 'N': Position (-1, 2) → Manhattan distance = 3
  • Move 'E': Position (0, 2) → Manhattan distance = 2

Hence, the maximum Manhattan distance achieved is 3.

---

Approach:

To solve this problem optimally, we can follow a greedy strategy. Here's how the approach works:

1. Track the movements: For each move, update the current position (x, y) by incrementing or decrementing the respective axis based on the direction of the move ('N', 'S', 'E', 'W').
2. Track the Manhattan distance: Calculate the Manhattan distance at each step.
3. Optimize the Manhattan distance: We are allowed to change up to k movements, so we need to maximize the impact of those changes. The greedy approach is to always change a movement that has the most impact on increasing the Manhattan distance.
4. Maximize the final distance: After iterating through all the moves, we calculate the maximum Manhattan distance by considering the best possible movements after k changes.

---

C++ Solution Code:

class Solution

{

public:

    int maxDistance(string s, int k)

    {

        int length = s.length();

        int up = 0, down = 0, right = 0, left = 0;

        int max_distance = 0;

        for (int index = 0; index < length; index++)

        {

            if (s[index] == 'N')

            {

                up++;

            }

            else if (s[index] == 'S')

            {

                down++;

            }

            else if (s[index] == 'E')

            {

                right++;

            }

            else if (s[index] == 'W')

            {

                left++;

            }

            int vertical_shift = abs(up - down);

            int horizontal_shift = abs(right - left);

            int base_distance = vertical_shift + horizontal_shift;

            int interfering_moves = min(up, down) + min(right, left);

            int max_possible_distance = base_distance + min(k, interfering_moves) * 2;

            max_distance = max(max_distance, min(index + 1, max_possible_distance));

        }

        return max_distance;

    }

};

Explanation:

1. Tracking Directions: We keep track of movements in four directions: up, down, right, and left.
2. Calculating Manhattan Distance: We calculate the Manhattan distance using the formula |x| + |y| for each position after every move.
3. Handling Changes: We check how the maximum possible distance can be adjusted by changing k moves. The interfering moves are the minimum of opposites (e.g., up vs down).
4. Maximizing Distance: After calculating the distance at each step, we update the maximum distance encountered.

---

Time Complexity:

• The solution iterates through the string once, updating variables and calculating distances in constant time.
• Time Complexity: O(n), where n is the length of the string s.

Space Complexity:

• The space complexity is constant since we are using a fixed amount of space for variables (up, down, right, left, etc.).
• Space Complexity: O(1).

Tags:

• #Leetcode
• #MaximumManhattanDistance
• #GreedyApproach
• #C++Solution
• #Algorithm
• #CodingInterview
• #CompetitiveProgramming
• #LeetcodeSolutions
• #DataStructures
• #ManhattanDistance