aboutsummaryrefslogtreecommitdiff
path: root/take_k_char_left_right.c
blob: 8838ec41ac009490bbd5a374f0f4601388470d6d (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
// 2516. Take K of Each Character From Left and Right
#include "leetcode.h"

/*
 * 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.
 */

bool check(int *arr, int *curr, int k) {
  if (curr[0] > arr[0] - k || curr[1] > arr[1] - k || curr[2] > arr[2] - k)
    return true;
  return false;
}

int takeCharacters(char *s, int k) {
  int n = strlen(s), arr[3] = {0};
  for (int i = 0; i < n; i++)
    arr[s[i] - 'a']++;
  if (arr[0] < k || arr[1] < k || arr[2] < k)
    return -1;
  int ans = n, window[3] = {0}, i = 0, j = 0;
  while (j < n) {
    window[s[j] - 'a']++;
    j++;
    while (check(arr, window, k)) {
      window[s[i] - 'a']--;
      i++;
    }
    ans = fmin(ans, n - (j - i));
  }
  return ans;
}

int main() {
  char *s1 = "aabaaaacaabc", *s2 = "a";
  printf("%d\n", takeCharacters(s1, 2)); // expect: 8
  printf("%d\n", takeCharacters(s2, 1)); // expect: -1
}