aboutsummaryrefslogtreecommitdiff
path: root/take_k_char_left_right.py
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.py
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.py')
-rw-r--r--take_k_char_left_right.py36
1 files changed, 36 insertions, 0 deletions
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))