aboutsummaryrefslogtreecommitdiff
path: root/can_make_palindrome_substr.c
blob: 700c5f2dbb0f245a9949f1f4a9b56b396dd0a8d1 (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
42
43
44
45
46
47
48
49
50
51
52
// 1177. Can Make Palindrome from Substring
#include "leetcode.h"

/*
 * you are given a string 's' and array 'queries' where 'queries[i] = [l_i,
 * r_i, k_i]'. we may rearrange the substring 's[l_i, ..., r_i]' for
 * each query and then choose up to 'k_i' f them to replace with any lowercase
 * english letter. if the substring is possible to be a palindrome string after
 * the operations above, the result of the query is 'true'. otherwise, the
 * result is 'false'. return a boolean array 'answer' where 'answer[i]' is the
 * result of the i'th query 'queries[i]'. note that each letter replacement is
 * counted individualy for replacement, so if, for example 's[l_i, ...,
 * r_i] = "aaa"', and 'k_i = 2', we can only replace two of the letters.
 * also note that no query modifies the initial string 's'.
 */

bool *canMakePaliQueries(char *s, int **queries, int queriesSize,
                         int *queriesColSize, int *returnSize) {
  int *dp = (int *)calloc(strlen(s), sizeof(int));
  bool *ans = (bool *)malloc(queriesSize * sizeof(bool));
  *returnSize = queriesSize;
  dp[0] = (1 << (s[0] - 'a'));
  for (int i = 1; i < strlen(s); i++)
    dp[i] = dp[i - 1] ^ (1 << (s[i] - 'a'));
  for (int i = 0; i < queriesSize; i++) {
    int l = queries[i][0], r = queries[i][1], k = queries[i][2], curr;
    curr = !l ? dp[r] : dp[r] ^ dp[l - 1];
    int one = __builtin_popcount(curr);
    ans[i] = one / 2 > k ? false : true;
  }
  free(dp);
  return ans;
}

int main() {
  char *s1 = "abcda", *s2 = "lyb";
  int q1i[5][3] = {{3, 3, 0}, {1, 2, 0}, {0, 3, 1}, {0, 3, 2}, {0, 4, 1}};
  int q2i[2][3] = {{0, 1, 0}, {2, 2, 1}}, rs1, rs2;
  struct two_d_arr q1, q2;
  two_d_arr_init(&q1, 5, 3, q1i);
  two_d_arr_init(&q2, 2, 3, q2i);
  bool *cmpq1 = canMakePaliQueries(s1, q1.arr, q1.row_size, q1.col_size, &rs1);
  bool *cmpq2 = canMakePaliQueries(s2, q2.arr, q2.row_size, q2.col_size, &rs2);
  for (int i = 0; i < rs1; i++)
    printf("%d ", cmpq1[i]); // expect: 1 0 0 1 1
  printf("\n");
  for (int i = 0; i < rs2; i++)
    printf("%d ", cmpq2[i]); // expect: 0 1
  printf("\n");
  free(cmpq1), free(cmpq2);
  two_d_arr_free(&q1), two_d_arr_free(&q2);
}