diff options
Diffstat (limited to 'max_manhattan_dist_k_change.c')
-rw-r--r-- | max_manhattan_dist_k_change.c | 39 |
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 +} |