[Leetcode] 3443. Maximum Manhattan Distance After K Changes
initial
the core issue that i missed out is max manhat dis may not necessarily occur at the end of the string. That is why i just initially thought oh just count freq of opposing directions (N vs S) and turn the minimum number to the non opposing direction by k amount
sol
we have to check for each step, wats the max manhat dist
For each character we count the frequency of that character and calc man hat distance. Now this is the core logic but we have to
maxDist = abs(dic['N']-dic['S'])+abs(dic['W']-dic['E'])
ans = max(ans, maxDist+min(2*k,i+1-maxDist ))whats this min()? we dont wanna overestimate the limit cuz maybe k is too small or even if we have enough k, there are no "wasted moves" (i.e. moves that dont cancel out each other) that cannot be turned to moves that increase our manhat distance.
For example
Example 1: Change limit is the bottleneck
String: "NNNNSSSS" at position 7
i + 1 = 8 moves made
diff = |4-4| + |0-0| = 0 (current distance)
Wasted moves = 8 - 0 = 8
We have k = 2 changes
min(2*2, 8) = min(4, 8) = 4
We're limited by our changes, not by wasted moves
Example 2: Wasted moves limit is the bottleneck
String: "NNNNNNNNS" at position 8
i + 1 = 9 moves made
diff = |8-1| + |0-0| = 7 (current distance)
Wasted moves = 9 - 7 = 2
We have k = 5 changes
min(2*5, 2) = min(10, 2) = 2
We're limited by wasted moves, not by changes
its 2*k cuz turning opposing direction to non opposing adds +2. the i+1-maxDist isnt really inutitive but its formula derived from pattern
class Solution:
def maxDistance(self, s: str, k: int) -> int:
ans=0
dic=defaultdict(int)
for i in range(len(s)):
c=s[i]
dic[c]+=1
maxDist = abs(dic['N']-dic['S'])+abs(dic['W']-dic['E'])
ans = max(ans, maxDist+min(2*k,i+1-maxDist ))
return ans
complexity
n time
1 space cuz dic stores just 4 constant keys
