Problem Description

Thinking process

Let's read the problem description first. It mentioned that we have a list of directions in sequence, given at most k times to change direction at any step. How far can you go from the base point in Manhattan distance?

Here are some insights I found after reading the problem description.

1. Our goal is to maximize the bigger number in abs(distance['N'] - distance['S']) and abs(distance['E'] - distance['W']). The notation of distance['N'] means how many 'N' appear in the trajectory.
2. How can we maximize the distance? The general idea is to change the steps from going backward to going forward. To be specific, change vertical_times = min(distance['S'], distance['N'], k) times for the vertical direction, or change horizontal_times = min(distance['W'], distance['E'], k-vertical_times) times for the horizontal distance.
3. How much will we improve from the original trajectory? We can contribute abs(dir1-dir2) + changes * 2 for both directions. And we can return the greater distance after their change as the final result.

Core algorithm implementation

Here is the core section for our program. For each step in the trajectory, we need to get the maximum possible distance.

maxDis = 0
for c in s:
            counter[c] = counter.get(c, 0) + 1
            vertical = min(min(counter.get('N',0), counter.get('S',0)), k) # modify times for N and S
            horizontal = min(min(counter.get('W',0), counter.get('E',0)), k-vertical) # modify times for W and E
            afterChange_v = changeDir(counter.get('N',0), counter.get('S',0), vertical)
            afterChange_h = changeDir(counter.get('W',0), counter.get('E',0), horizontal)
            maxDis = max(afterChange_v+afterChange_h, maxDis)
return maxDis

Time complexity O(n)

Since we need to go through each position in the traversal and change direction. The time complexity is O(nt), where n is the number of directions in the string and t is the time complexity of changing direction.

But since changing direction only involves a simple mathematical calculation, it only has linear time complexity. So the time complexity is O(n).

Space complexity O(1)

There is only a counter that may have the count for 4 directions, which doesn't expand according to the dataset size. So the space complexity is O(1).

Full solution

class Solution:
    def maxDistance(self, s: str, k: int) -> int:
        def changeDir(dir1, dir2, changes):
            res = abs(dir1-dir2) + changes * 2
            return res
        counter = {}
        maxDis = 0
        for c in s:
            counter[c] = counter.get(c, 0) + 1
            vertical = min(min(counter.get('N',0), counter.get('S',0)), k) # modify times for N and S
            horizontal = min(min(counter.get('W',0), counter.get('E',0)), k-vertical) # modify times for W and E
            afterChange_v = changeDir(counter.get('N',0), counter.get('S',0), vertical)
            afterChange_h = changeDir(counter.get('W',0), counter.get('E',0), horizontal)
            maxDis = max(afterChange_v+afterChange_h, maxDis)

        return maxDis