aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
-rw-r--r--can_make_palindrome_substr.c52
-rw-r--r--can_make_palindrome_substr.py40
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]]))