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