aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
-rw-r--r--take_k_char_left_right.c41
-rw-r--r--take_k_char_left_right.py36
2 files changed, 77 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
+}
diff --git a/take_k_char_left_right.py b/take_k_char_left_right.py
new file mode 100644
index 0000000..3d9d32e
--- /dev/null
+++ b/take_k_char_left_right.py
@@ -0,0 +1,36 @@
+# 2516. Take K of Each Character From Left and Right
+
+"""
+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.
+"""
+
+
+class Solution(object):
+ def takeCharacters(self, s, k):
+ """
+ :type s: str
+ :type k: int
+ :rtype: int
+ """
+ lim = {c: s.count(c) - k for c in "abc"}
+ if any(x < 0 for x in lim.values()):
+ return -1
+ cnts = {c: 0 for c in "abc"}
+ ans, l = 0, 0
+ for r, c in enumerate(s):
+ cnts[c] += 1
+ while cnts[c] > lim[c]:
+ cnts[s[l]] -= 1
+ l += 1
+ ans = max(ans, r - l + 1)
+ return len(s) - ans
+
+
+if __name__ == "__main__":
+ obj = Solution()
+ print(obj.takeCharacters(s="aabaaaacaabc", k=2))
+ print(obj.takeCharacters(s="a", k=1))