diff options
-rw-r--r-- | can_make_palindrome_substr.c | 52 | ||||
-rw-r--r-- | can_make_palindrome_substr.py | 40 |
2 files changed, 92 insertions, 0 deletions
diff --git a/can_make_palindrome_substr.c b/can_make_palindrome_substr.c new file mode 100644 index 0000000..700c5f2 --- /dev/null +++ b/can_make_palindrome_substr.c @@ -0,0 +1,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); +} diff --git a/can_make_palindrome_substr.py b/can_make_palindrome_substr.py new file mode 100644 index 0000000..10f8f25 --- /dev/null +++ b/can_make_palindrome_substr.py @@ -0,0 +1,40 @@ +# 1177. Can Make Palindrome from Substring + +""" +you are given a string 's' and array 'queries' where 'queries[i] = [left_i, +right_i, k_i]'. we may rearrange the substring 's[left_i, ..., right_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[left_i, ..., +right_i] = "aaa"', and 'k_i = 2', we can only replace two of the letters. +also note that no query modifies the initial string 's'. +""" + + +class Solution(object): + def canMakePaliQueries(self, s, queries): + """ + :type s: str + :type queries: List[List[int]] + :rtype: List[bool] + """ + n, m = 26, len(s) + 1 + ints = list(map(lambda x: ord(x) - ord("a"), s)) + dp = [0] * m + for i in range(1, m): + dp[i] = dp[i - 1] ^ (1 << ints[i - 1]) + ones = lambda x: bin(x).count("1") + return [ones(dp[r + 1] ^ dp[l]) >> 1 <= k for l, r, k in queries] + + +if __name__ == "__main__": + obj = Solution() + print( + obj.canMakePaliQueries( + s="abcda", queries=[[3, 3, 0], [1, 2, 0], [0, 3, 1], [0, 3, 2], [0, 4, 1]] + ) + ) + print(obj.canMakePaliQueries(s="lyb", queries=[[0, 1, 0], [2, 2, 1]])) |