2516-take-k-of-each-character-from-left-and-right.rs - leetcode

	leetcode Leetcode problem solutions
	git clone https://git.sinitax.com/sinitax/leetcode
	Log \| Files \| Refs \| sfeed.txt
2516-take-k-of-each-character-from-left-and-right.rs (2729B)
      1/// 2516. Take K of Each Character From Left and Right (Medium)
      2///
      3/// You are given a string s consisting of the characters 'a', 'b', and 'c' and
      4/// a non-negative integer k. Each minute, you may take either the *leftmost*
      5/// character of s, or the *rightmost* character of s.
      6///
      7/// Return the *minimum* number of minutes needed for you to take *at least* k
      8/// of each character, or return -1 if it is not possible to take k of each
      9/// character.
     10///
     11/// *Example 1:*
     12///
     13///   *Input:* s = "aabaaaacaabc", k = 2
     14///   *Output:* 8
     15///   *Explanation:*
     16///   Take three characters from the left of s. You now have two 'a' characters,
     17///   and one 'b' character.
     18///   Take five characters from the right of s. You now have four 'a' characters,
     19///   two 'b' characters, and two 'c' characters.
     20///   A total of 3 + 5 = 8 minutes is needed.
     21///   It can be proven that 8 is the minimum number of minutes needed.
     22///
     23/// *Example 2:*
     24///
     25///   *Input:* s = "a", k = 1
     26///   *Output:* -1
     27///   *Explanation:* It is not possible to take one 'b' or 'c' so return -1.
     28///
     29/// *Constraints:*
     30///
     31///   * 1 <= s.length <= 105
     32///   * s consists of only the letters 'a', 'b', and 'c'.
     33///   * 0 <= k <= s.length
     34///
     35use leetcode::*;
     36
     37struct Solution {}
     38
     39impl Solution {
     40    pub fn take_characters(s: String, k: i32) -> i32 {
     41        let nums = s.as_bytes();
     42        let k = k as usize;
     43        let n = nums.len();
     44        let (mut left, mut right) = (0, 0);
     45        let mut counts = [0usize; 3];
     46        let mut min_count = 0usize;
     47        let mut answer = n + 1;
     48        while left < n && min_count < k {
     49            counts[(nums[left] - 0x61) as usize] += 1;
     50            left += 1;
     51            min_count = *counts.iter().min().unwrap();
     52        }
     53        if min_count == k {
     54            answer = left;
     55        }
     56        while left > 0 {
     57            left -= 1;
     58            counts[(nums[left] - 0x61) as usize] -= 1;
     59            min_count = *counts.iter().min().unwrap();
     60            while right < n - left && min_count < k {
     61                counts[(nums[n - 1 - right] - 0x61) as usize] += 1;
     62                right += 1;
     63                min_count = *counts.iter().min().unwrap();
     64            }
     65            if min_count == k {
     66                answer = answer.min(left + right);
     67            }
     68        }
     69        if answer <= n {
     70            answer as i32
     71        } else {
     72            -1
     73        }
     74    }
     75}
     76
     77pub fn main() {
     78    println!("{}", Solution::take_characters(arg(1), arg_into(2)));
     79}
     80
     81#[cfg(test)]
     82mod tests {
     83    use crate::Solution;
     84
     85    #[test]
     86    fn test() {
     87        assert_eq!(Solution::take_characters("aabaaaacaabc".to_string(), 2), 8);
     88        assert_eq!(Solution::take_characters("a".to_string(), 1), -1);
     89    }
     90}