Take k of each character from left and right

Hash Table String Sliding Window

51.5% acceptance

Feb 25, 2026

1521

172

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.

Solution

Rust

Time O(n²)

Space O(1)

LeetCode

solution.rs

impl Solution {
  pub fn take_characters(s: String, k: i32) -> i32 {
    if k == 0 {
      return 0;
    }
    let s: Vec<u8> = s.bytes().collect();
    let n = s.len();
    let mut total = [0i32; 3];
    for &c in &s {
      total[(c - b'a') as usize] += 1;
    }
    if total.iter().any(|&x| x < k) {
      return -1;
    }
    // Find maximum window [left, right] we can skip
    // such that total[i] - window[i] >= k for all i
    let mut window = [0i32; 3];
    let mut max_window = 0usize;
    let mut left = 0usize;
    for right in 0..n {
      window[(s[right] - b'a') as usize] += 1;
      while (0..3).any(|i| total[i] - window[i] < k) {
        window[(s[left] - b'a') as usize] -= 1;
        left += 1;
      }
      max_window = max_window.max(right + 1 - left);
    }
    (n - max_window) as i32
  }
}