leetcode

commit 5dff7aff23df1e8b2a2a817799ee7c9c27b789f1
parent 56a1e31495c2a3ceb42495e3c341f8af676fc087
Author: Louis Burda <quent.burda@gmail.com>
Date:   Wed, 20 Nov 2024 22:10:56 +0100

Add problem 2516

Diffstat:
M
Cargo.toml
 | 
4
++++
A
src/bin/2516-take-k-of-each-character-from-left-and-right.rs
 | 
91
+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++

2 files changed, 95 insertions(+), 0 deletions(-)
diff --git a/Cargo.toml b/Cargo.toml
@@ -16,6 +16,10 @@ name = "2070"
 path = "src/bin/2070-most-beautiful-item-for-each-query.rs"
 
 [[bin]]
+name = "2516"
+path = "src/bin/2516-take-k-of-each-character-from-left-and-right.rs"
+
+[[bin]]
 name = "2463"
 path = "src/bin/2463-minimum-total-distance-traveled.rs"
 
diff --git a/src/bin/2516-take-k-of-each-character-from-left-and-right.rs b/src/bin/2516-take-k-of-each-character-from-left-and-right.rs
@@ -0,0 +1,91 @@
+/// 2516. Take K of Each Character From Left and Right (Medium)
+///
+/// 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 to take k of each
+/// character.
+///
+/// *Example 1:*
+///
+///   *Input:* s = "aabaaaacaabc", k = 2
+///   *Output:* 8
+///   *Explanation:*
+///   Take three characters from the left of s. You now have two 'a' characters,
+///   and one 'b' character.
+///   Take five characters from the right of s. You now have four 'a' characters,
+///   two 'b' characters, and two 'c' characters.
+///   A total of 3 + 5 = 8 minutes is needed.
+///   It can be proven that 8 is the minimum number of minutes needed.
+///
+/// *Example 2:*
+///
+///   *Input:* s = "a", k = 1
+///   *Output:* -1
+///   *Explanation:* It is not possible to take one 'b' or 'c' so return -1.
+///
+/// *Constraints:*
+///
+///   * 1 <= s.length <= 105
+///   * s consists of only the letters 'a', 'b', and 'c'.
+///   * 0 <= k <= s.length
+///
+
+use leetcode::*;
+
+struct Solution {}
+
+impl Solution {
+    pub fn take_characters(s: String, k: i32) -> i32 {
+        let nums = s.as_bytes();
+        let k = k as usize;
+        let n = nums.len();
+        let (mut left, mut right) = (0, 0);
+        let mut counts = [0usize; 3];
+        let mut min_count = 0usize;
+        let mut answer = n+1;
+        while left < n && min_count < k {
+            counts[(nums[left]-0x61) as usize] += 1;
+            left += 1;
+            min_count = *counts.iter().min().unwrap();
+        }
+        if min_count == k {
+            answer = left;
+        }
+        while left > 0 {
+            left -= 1;
+            counts[(nums[left]-0x61) as usize] -= 1;
+            min_count = *counts.iter().min().unwrap();
+            while right < n - left && min_count < k {
+                counts[(nums[n-1-right]-0x61) as usize] += 1;
+                right += 1;
+                min_count = *counts.iter().min().unwrap();
+            }
+            if min_count == k {
+                answer = answer.min(left + right);
+            }
+        }
+        if answer <= n {
+            answer as i32
+        } else {
+            -1
+        }
+    }
+}
+
+pub fn main() {
+    println!("{}", Solution::take_characters(arg(1), arg_into(2)));
+}
+
+#[cfg(test)]
+mod tests {
+    use crate::Solution;
+
+    #[test]
+    fn test() {
+        assert_eq!(Solution::take_characters("aabaaaacaabc".to_string(), 2), 8);
+        assert_eq!(Solution::take_characters("a".to_string(), 1), -1);
+    }
+}