diff options
author | Jack Sangdahl <[email protected]> | 2025-06-19 19:21:40 -0600 |
---|---|---|
committer | Jack Sangdahl <[email protected]> | 2025-06-19 19:21:40 -0600 |
commit | a032c2f9c7e06b0402ba2675f96830a0bf80b71e (patch) | |
tree | 25976ffd4b71d3e38c6d8da0d49a6f3a8e933a4b /max_manhattan_dist_k_change.py | |
parent | d164977cebec7be669ff3c0beb9703b89efbb6b2 (diff) | |
download | leetcode-master.tar.gz leetcode-master.zip |
Diffstat (limited to 'max_manhattan_dist_k_change.py')
-rw-r--r-- | max_manhattan_dist_k_change.py | 35 |
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)) |