diff options
author | Jack Sangdahl <[email protected]> | 2024-11-19 19:48:32 -0700 |
---|---|---|
committer | Jack Sangdahl <[email protected]> | 2024-11-19 19:48:32 -0700 |
commit | fe078c7bdfc6a6a339c44a422bf5ca98130bf94a (patch) | |
tree | 6e4b1041230ccc5b8f03386b4093bd8ffa39f4c0 /take_k_char_left_right.py | |
parent | 4567a1b9e6047a644690115acd26fd2de32d3645 (diff) | |
download | leetcode-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.py | 36 |
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)) |