aboutsummaryrefslogtreecommitdiff
path: root/take_k_char_left_right.c
diff options
context:
space:
mode:
authorJack Sangdahl <[email protected]>2024-11-19 19:48:32 -0700
committerJack Sangdahl <[email protected]>2024-11-19 19:48:32 -0700
commitfe078c7bdfc6a6a339c44a422bf5ca98130bf94a (patch)
tree6e4b1041230ccc5b8f03386b4093bd8ffa39f4c0 /take_k_char_left_right.c
parent4567a1b9e6047a644690115acd26fd2de32d3645 (diff)
downloadleetcode-fe078c7bdfc6a6a339c44a422bf5ca98130bf94a.tar.gz
leetcode-fe078c7bdfc6a6a339c44a422bf5ca98130bf94a.zip
2516. take k of each character from left and right
Diffstat (limited to 'take_k_char_left_right.c')
-rw-r--r--take_k_char_left_right.c41
1 files changed, 41 insertions, 0 deletions
diff --git a/take_k_char_left_right.c b/take_k_char_left_right.c
new file mode 100644
index 0000000..8838ec4
--- /dev/null
+++ b/take_k_char_left_right.c
@@ -0,0 +1,41 @@
+// 2516. Take K of Each Character From Left and Right
+#include "leetcode.h"
+
+/*
+ * you are given a string 's' consisting of the characters 'a', 'b', and 'c' and
+ * a non-negative integer 'k'. each minute you may take either the leftmost
+ * character of 's' or the rightmost character of 's'. return the minimum number
+ * of minutes needed for you to take at least 'k' of each character, or return
+ * -1 if it is not possible t to take 'k' of each character.
+ */
+
+bool check(int *arr, int *curr, int k) {
+ if (curr[0] > arr[0] - k || curr[1] > arr[1] - k || curr[2] > arr[2] - k)
+ return true;
+ return false;
+}
+
+int takeCharacters(char *s, int k) {
+ int n = strlen(s), arr[3] = {0};
+ for (int i = 0; i < n; i++)
+ arr[s[i] - 'a']++;
+ if (arr[0] < k || arr[1] < k || arr[2] < k)
+ return -1;
+ int ans = n, window[3] = {0}, i = 0, j = 0;
+ while (j < n) {
+ window[s[j] - 'a']++;
+ j++;
+ while (check(arr, window, k)) {
+ window[s[i] - 'a']--;
+ i++;
+ }
+ ans = fmin(ans, n - (j - i));
+ }
+ return ans;
+}
+
+int main() {
+ char *s1 = "aabaaaacaabc", *s2 = "a";
+ printf("%d\n", takeCharacters(s1, 2)); // expect: 8
+ printf("%d\n", takeCharacters(s2, 1)); // expect: -1
+}