Editorial

Solution walkthrough

Review the explanation, then compare the reference implementation.

Video explanation

Solution

Intuition

Manhattan distance is the maximum of four signed coordinate sums. For any one of those directions, two move letters contribute +1 and the other two contribute -1. Changing an unfavorable move into a favorable one improves that signed distance by two.

Approach

Scan the string separately for NW, NE, SW, and SE, resetting the change budget each time. A move belonging to the chosen pair increases the current signed distance. For an unfavorable move, spend one remaining change to make it increase instead; once the budget is exhausted, it decreases the distance.

Update the answer after every prefix, because the maximum may occur before the final position. Spending changes on the earliest unfavorable moves optimizes every processed prefix: all such corrections have identical gain, and later moves cannot affect an earlier position. Taking the maximum over the four direction pairs recovers the best Manhattan distance achievable at any time.

class Solution:
    def maxDistance(self, s: str, k: int) -> int:
        res = 0

        for dir in ('NW', 'NE', 'SW', 'SE'):
            kk = k
            dist = 0
            for c in s:
                if c in dir or kk:
                    dist += 1
                    if not c in dir: kk -= 1
                else:
                    dist -= 1
                res = max(res, dist)

        return res

Complexity analysis

Let n = s.length. Four constant direction-pair scans take O(4n) = O(n) time and O(1) auxiliary space. Both solutions update the maximum after every prefix.