Maximum Manhattan Distance After K Changes

When I saw this question, I believed that the intended solution was a simulation question.

For one, this is due to the lenient constraint of 1 <= s.length <= 10^5 and because there are so many different edge cases in this problem, that there are not any obvious improvements that we can make (since we have to iterate through the entirety of s in most test-cases anyways).

Therefore, my algorithm hinges on iterating through s and keeping track of how many times we have moved in each direction.

At each index, we update the direction array, where:

1. direction[0] stores N
2. direction[1] stores S
3. direction[2] stores E
4. direction[3] stores W

Then, for each pair (there exists 2 pairs; N with S and E with W) we need to find the direction that has a lower frequency

• for example, if direction = {9, 5, 2, 6}, then the directions in each pair with a lower frequency is:
  • S < N since 5 <= 9
  • E < W since 2 <= 6
• and then sum both frequencies together -> minFrequencySum

Next, we calculate the maximum number of letters we can convert:

• we will either be able to convert k letters or the sum of the letters in directions of each pair with a lower frequency
• e.g. difference = min(k, minFrequencySum);

Finally, we see if this answer is the maximum manhattan distance after k changes

• note, that if we convert n letters, we add 2n to the manhattan distance
• e.g. ans = max(ans, abs(NCount - SCount) + abs(ECount - WCount) + 2*difference);

Then, we repeat this process for every index in the array.

code

class Solution {
private:
    int direction[4] = {0};
    void updateDistance(char& d) {
        if (d == 'N') {
            ++direction[0];
        } else if (d == 'S') {
            ++direction[1];
        } else if (d == 'E') {
            ++direction[2];
        } else if (d == 'W') {
            ++direction[3];
        }
    }
public:
    int maxDistance(string s, int k) {
        int ans = 0;
        for (int i = 0; i < s.size(); ++i) {
            updateDistance(s[i]);

            int minVerticalIndex = 0;
            if (direction[0] > direction [1]) {
                minVerticalIndex = 1;
            }
            int minHorizontalIndex = 2;
            if (direction[2] > direction [3]) {
                minHorizontalIndex = 3;
            }

            int difference = min(k, direction[minVerticalIndex] + direction[minHorizontalIndex]);

            ans = max(ans, abs(direction[1]-direction[0]) + abs(direction[3]-direction[2]) + 2*difference);
        }
        return ans;
    }
};

complexity

• Time: O(n) where n is the size of s
• Space: O(1)

time taken

• 9 minutes and 3 seconds