aboutsummaryrefslogtreecommitdiff
path: root/get_equal_substr_budget.c
blob: 0a515f8d24b8c00bf9e5b3dd4e5e30052f9e2fd2 (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
40
// 1208. Get Equal Substrings Within Budget
#include "leetcode.h"

/*
 * you are given two strings 's' and 't' of the same length and an integer
 * 'maxCost'. you want to change 's' to 't'. changing the i'th character of 's'
 * to the i'th character of 't' costs '|s[i] - t[i]|'. return the maximum length
 * of a substring of 's' that can be changed to be the same as the corresponding
 * substring of 't' with a cost less than or equal to 'maxCost'. if there is no
 * substring from 's' that can be changed to its corresponding substring from
 * 't', return 0
 */

int equalSubstring(char *s, char *t, int maxCost) {
  int n = strlen(s), ans = 0, sum = 0, l = 0, r;
  char *diff = (char *)malloc(n * sizeof(char));
  for (int i = 0; i < n; i++)
    diff[i] = abs(s[i] - t[i]);
  for (r = 0; r < n; r++) {
    sum += diff[r];
    if (sum > maxCost) {
      ans = fmax(ans, r - l);
      while (sum > maxCost) {
        sum -= diff[l];
        l++;
      }
    }
  }
  ans = fmax(ans, r - l);
  free(diff);
  return ans;
}

int main() {
  char *s1 = "abcd", *t1 = "bcdf", *s2 = "abcd", *t2 = "cdef", *s3 = "abcd",
       *t3 = "acde";
  printf("%d\n", equalSubstring(s1, t1, 3)); // expect: 3
  printf("%d\n", equalSubstring(s2, t2, 3)); // expect: 1
  printf("%d\n", equalSubstring(s3, t3, 0)); // expect: 1
}