aboutsummaryrefslogtreecommitdiff
path: root/max_manhattan_dist_k_change.py
diff options
context:
space:
mode:
authorJack Sangdahl <[email protected]>2025-06-19 19:21:40 -0600
committerJack Sangdahl <[email protected]>2025-06-19 19:21:40 -0600
commita032c2f9c7e06b0402ba2675f96830a0bf80b71e (patch)
tree25976ffd4b71d3e38c6d8da0d49a6f3a8e933a4b /max_manhattan_dist_k_change.py
parentd164977cebec7be669ff3c0beb9703b89efbb6b2 (diff)
downloadleetcode-master.tar.gz
leetcode-master.zip
3443. maximum manhattan distance after k changesHEADmaster
Diffstat (limited to 'max_manhattan_dist_k_change.py')
-rw-r--r--max_manhattan_dist_k_change.py35
1 files changed, 35 insertions, 0 deletions
diff --git a/max_manhattan_dist_k_change.py b/max_manhattan_dist_k_change.py
new file mode 100644
index 0000000..5bb0ee2
--- /dev/null
+++ b/max_manhattan_dist_k_change.py
@@ -0,0 +1,35 @@
+# 3443. Maximum Manhattan Distance After K Changes
+
+"""
+you are given a sing 's' consisting of the characters 'N', 'S', 'E', and
+'W', where 's[i]' indicates movements in an infinite grid, where each letter
+is a move of 1 unit in that cardinal direction. initially, you are at the
+origin '(0, 0)'. you can change at most 'k' characters to any of the four
+directions. find the maximum manhattan distance from the origin that can be
+achieved at any time while performing the movements in order.
+"""
+
+
+class Solution(object):
+ def maxDistance(self, s, k):
+ """
+ :type s: str
+ :type k: int
+ :rtype: int
+ """
+ ans = 0
+ for i in [{"N", "E"}, {"N", "W"}, {"S", "E"}, {"S", "W"}]:
+ curr_dist, curr_k = 0, k
+ for j in s:
+ curr_dist += 1
+ curr_k -= j not in i
+ else:
+ curr_dist -= 1
+ ans = max(ans, curr_dist)
+ return ans
+
+
+if __name__ == "__main__":
+ obj = Solution()
+ print(obj.maxDistance(s="NWSE", k=1))
+ print(obj.maxDistance(s="NSWWEW", k=3))