aboutsummaryrefslogtreecommitdiff
path: root/get_equal_substr_budget.c
diff options
context:
space:
mode:
Diffstat (limited to 'get_equal_substr_budget.c')
-rw-r--r--get_equal_substr_budget.c40
1 files changed, 40 insertions, 0 deletions
diff --git a/get_equal_substr_budget.c b/get_equal_substr_budget.c
new file mode 100644
index 0000000..0a515f8
--- /dev/null
+++ b/get_equal_substr_budget.c
@@ -0,0 +1,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
+}