aboutsummaryrefslogtreecommitdiff
path: root/min_window_substring.c
diff options
context:
space:
mode:
Diffstat (limited to 'min_window_substring.c')
-rw-r--r--min_window_substring.c67
1 files changed, 67 insertions, 0 deletions
diff --git a/min_window_substring.c b/min_window_substring.c
new file mode 100644
index 0000000..efcd3a5
--- /dev/null
+++ b/min_window_substring.c
@@ -0,0 +1,67 @@
+// 76. Minimum Window Substring
+#include "leetcode.h"
+
+/*
+ * given two strings 's' and 't' of length 'n' and 'm' respectively, return the
+ * minimum window substring of 's' such that every character in 't' (including
+ * duplicates) is included in the window. if there is no such substring, return
+ * the empty string. the testcases will be generated such that the answer is
+ * unique.
+ */
+
+char *minWindow(char *s, char *t) {
+ int m = strlen(s), n = strlen(t), min = INT_MAX, l = -1, r, match = 0,
+ a_idx = -1, r_key, l_key;
+ int *alpha = calloc(52, sizeof(int));
+ int *alpha_copy = calloc(52, sizeof(int));
+ for (int i = 0; i < n; i++)
+ (t[i] >= 'a') ? alpha[t[i] - 'a']++ : alpha[t[i] - 'A' + 26]++;
+
+ for (r = 0; r < m; r++) {
+ r_key = (s[r] >= 'a') ? r_key = s[r] - 'a' : s[r] - 'A' + 26;
+
+ if (alpha[r_key]) {
+ if (l == -1)
+ l = r;
+ alpha_copy[r_key]++;
+ if (alpha_copy[r_key] <= alpha[r_key]) {
+ match++;
+ if (match == n) {
+ l_key = (s[l] >= 'a') ? s[l] - 'a' : s[l] - 'A' + 26;
+ while (match == n || !alpha[l_key]) {
+ if (alpha[l_key]) {
+ alpha_copy[l_key]--;
+ if (alpha_copy[l_key] < alpha[l_key]) {
+ if ((r - l + 1) < min) {
+ min = r - l + 1;
+ a_idx = l;
+ }
+ match--;
+ }
+ }
+ l++;
+ if (l < m)
+ l_key = (s[l] >= 'a') ? s[l] - 'a' : s[l] - 'A' + 26;
+ else
+ break;
+ }
+ }
+ }
+ }
+ }
+ if (a_idx == -1)
+ return "";
+ char *ans = malloc((min + 1) * sizeof(char));
+ ans[min] = '\0';
+ strncpy(ans, &s[a_idx], min);
+ return ans;
+}
+
+int main() {
+ char *s1 = "ADOBECODEBANC", *t1 = "ABC";
+ char *s2 = "a", *t2 = "a";
+ char *s3 = "a", *t3 = "aa";
+ printf("%s\n", minWindow(s1, t1)); // expect: BANC
+ printf("%s\n", minWindow(s2, t2)); // expect: a
+ printf("%s\n", minWindow(s3, t3)); // expect: null
+}