aboutsummaryrefslogtreecommitdiff
path: root/max_manhattan_dist_k_change.c
blob: 70e735a663dc179d2560a1acca36aea9e424f729 (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
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
}