aboutsummaryrefslogtreecommitdiff
path: root/max_manhattan_dist_k_change.c
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.c
parentd164977cebec7be669ff3c0beb9703b89efbb6b2 (diff)
downloadleetcode-master.tar.gz
leetcode-master.zip
3443. maximum manhattan distance after k changesHEADmaster
Diffstat (limited to 'max_manhattan_dist_k_change.c')
-rw-r--r--max_manhattan_dist_k_change.c39
1 files changed, 39 insertions, 0 deletions
diff --git a/max_manhattan_dist_k_change.c b/max_manhattan_dist_k_change.c
new file mode 100644
index 0000000..70e735a
--- /dev/null
+++ b/max_manhattan_dist_k_change.c
@@ -0,0 +1,39 @@
+// 3443. Maximum Manhattan Distance After K Changes
+#include "leetcode.h"
+
+/*
+ * 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.
+ */
+
+int maxDistance(char *s, int k) {
+ const char dir[4][2] = {{'N', 'E'}, {'N', 'W'}, {'S', 'E'}, {'S', 'W'}};
+ int ans = 0;
+ for (int i = 0; i < 4; i++) {
+ bool set[1 << (CHAR_BIT - 1)] = {0};
+ set[dir[i][0]] = set[dir[i][1]] = true;
+ int curr_dist = 0, curr_k = k;
+ for (int j = 0; s[j] != '\0'; j++) {
+ if (!set[s[j]] && !(curr_k >= 1)) {
+ curr_dist--;
+ continue;
+ }
+ if (!set[s[j]])
+ curr_k--;
+ curr_dist++;
+ if (curr_dist > ans)
+ ans = curr_dist;
+ }
+ }
+ return ans;
+}
+
+int main() {
+ char *s1 = "NWSE", *s2 = "NSWWEW";
+ printf("%d\n", maxDistance(s1, 1)); // expect: 3
+ printf("%d\n", maxDistance(s2, 3)); // expect: 6
+}