aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
-rw-r--r--count_and_say.c68
-rw-r--r--count_and_say.py35
-rw-r--r--count_equal_div_pair_arr.c23
-rw-r--r--count_equal_div_pair_arr.py37
-rw-r--r--count_hidden_sequences.c29
-rw-r--r--count_hidden_sequences.py30
-rw-r--r--count_num_fair_pairs.c51
-rw-r--r--count_num_fair_pairs.py5
-rw-r--r--count_num_good_subarr.c94
-rw-r--r--count_num_good_subarr.py35
-rw-r--r--count_num_ideal_arr.c36
-rw-r--r--count_num_ideal_arr.py38
-rw-r--r--max_product_len_palindrome_subseq.c46
-rw-r--r--max_product_len_palindrome_subseq.py46
-rw-r--r--rabbits_in_forest.c36
-rw-r--r--rabbits_in_forest.py30
-rw-r--r--substring_xor_queries.c137
-rw-r--r--substring_xor_queries.py43
18 files changed, 735 insertions, 84 deletions
diff --git a/count_and_say.c b/count_and_say.c
index 8d186fc..95726cd 100644
--- a/count_and_say.c
+++ b/count_and_say.c
@@ -1,7 +1,5 @@
// 38. Count and Say
-#include <stdio.h>
-#include <stdlib.h>
-#include <string.h>
+#include "leetcode.h"
/*
* the count-and-say sequence is a sequence of digit strings defined by the
@@ -16,53 +14,33 @@
* term of the count and say sequence.
*/
-char *int_to_char(int n) {
- char *res = malloc(11);
- res[10] = '\0';
- int idx = 9;
- while (n) {
- res[idx] = '0' + n % 10;
- n /= 10;
- idx--;
- }
- return &res[idx + 1];
-}
-
char *countAndSay(int n) {
- char *curr = malloc(5000), *post = malloc(5000);
- curr[0] = '1';
- curr[1] = '\0';
if (n == 1)
- return curr;
- for (int i = 2; i <= n; i++) {
- int curr_len = strlen(curr), idx = 0, cnt = 1, pos = 0;
- char *tmp;
- for (int j = 1; j < curr_len; j++) {
- if (curr[j] == curr[j - 1])
- cnt++;
- else {
- tmp = int_to_char(cnt);
- strncpy(&post[pos], tmp, strlen(tmp));
- pos += strlen(tmp);
- post[pos] = curr[j - 1];
- pos++;
- cnt = 1;
- }
+ return "1";
+ char *s = countAndSay(n - 1), curr = *s;
+ char *ans = (char *)malloc(4463 * sizeof(char));
+ int m = strlen(s), idx = 0, cnt = 1;
+ for (int i = 1; i < m; i++) {
+ char c = *(s + i);
+ if (c == curr)
+ cnt++;
+ else {
+ *(ans + idx++) = ('0' + cnt);
+ *(ans + idx++) = curr;
+ curr = c;
+ cnt = 1;
}
- tmp = int_to_char(cnt);
- strncpy(&post[pos], tmp, strlen(tmp));
- pos += strlen(tmp);
- post[pos] = curr[curr_len - 1];
- pos++;
- post[pos] = '\0';
- tmp = curr;
- curr = post;
- post = tmp;
}
- return curr;
+ *(ans + idx++) = ('0' + cnt);
+ *(ans + idx++) = curr;
+ *(ans + idx) = '\0';
+ return ans;
}
int main() {
- printf("%s\n", countAndSay(1)); // expect: 1
- printf("%s\n", countAndSay(4)); // expect: 1211
+ char *cas1 = countAndSay(4), *cas2 = countAndSay(1);
+ printf("%s\n", cas1); // expect: 1211
+ printf("%s\n", cas2); // expect: 1
+ free(cas1);
+ free(cas2);
}
diff --git a/count_and_say.py b/count_and_say.py
new file mode 100644
index 0000000..e8521b3
--- /dev/null
+++ b/count_and_say.py
@@ -0,0 +1,35 @@
+# 38. Count and Say
+from re import findall
+
+"""
+the count-and-say sequence is a sequence of digit strings defined by the
+recursive formula:
+- countAndSay(1) = "1"
+- countAndSay(n) is the way you would "say" the digit string from
+'countAndSay(n - 1)', which is then converted into a different digit string
+to determine how you "say" a digit string, split it into minimal number of
+substrings such that each substring contains exactly one unique digit. then
+for each substring, say the number of digits, then say the digit, finally,
+concatenate every said digit. given a positive integer 'n', return the n'th
+term of the count and say sequence.
+"""
+
+
+class Solution(object):
+ def countAndSay(self, n):
+ """
+ :type n: int
+ :rtype: str
+ """
+ ans = "1"
+ for _ in range(n - 1):
+ ans = "".join(
+ str(len(group)) + digit for group, digit in findall(r"((.)\2*)", ans)
+ )
+ return ans
+
+
+if __name__ == "__main__":
+ obj = Solution()
+ print(obj.countAndSay(n=4))
+ print(obj.countAndSay(n=1))
diff --git a/count_equal_div_pair_arr.c b/count_equal_div_pair_arr.c
new file mode 100644
index 0000000..d6aeb12
--- /dev/null
+++ b/count_equal_div_pair_arr.c
@@ -0,0 +1,23 @@
+// 2176. Count Equal and Divisible Pairs in an Array
+#include "leetcode.h"
+
+/*
+ * given a 0-indexed integer array 'nums' of length 'n' and an integer 'k',
+ * return the number of pairs '(i, j)' where '0 <= i < j < n' such that 'nums[i]
+ * == nums[j]' and '(i * j)' is divisble by 'k'.
+ */
+
+int countPairs(int *nums, int numsSize, int k) {
+ int cnt = 0;
+ for (int i = 0; i < numsSize; i++)
+ for (int j = i + 1; j < numsSize; j++)
+ if (nums[i] == nums[j] && !((i * j) % k))
+ cnt++;
+ return cnt;
+}
+
+int main() {
+ int n1[] = {3, 1, 2, 2, 2, 1, 3}, n2[] = {1, 2, 3, 4};
+ printf("%d\n", countPairs(n1, ARRAY_SIZE(n1), 2)); // expect: 4
+ printf("%d\n", countPairs(n2, ARRAY_SIZE(n2), 1)); // expect: 0
+}
diff --git a/count_equal_div_pair_arr.py b/count_equal_div_pair_arr.py
new file mode 100644
index 0000000..84d4a55
--- /dev/null
+++ b/count_equal_div_pair_arr.py
@@ -0,0 +1,37 @@
+# 2176. Count Equal and Divisible Pairs in an Array
+import collections
+from math import gcd
+
+"""
+given a 0-indexed integer array 'nums' of length 'n' and an integer 'k',
+return the number of pairs '(i, j)' where '0 <= i < j < n' such that 'nums[i]
+== nums[j]' and '(i * j)' is divisble by 'k'.
+"""
+
+
+class Solution(object):
+ def countPairs(self, nums, k):
+ """
+ :type nums: List[int]
+ :type k: int
+ :rtype: int
+ """
+ ids = collections.defaultdict(list)
+ for i, j in enumerate(nums):
+ ids[j].append(i)
+ ans = 0
+ for i in ids.values():
+ gcds = collections.Counter()
+ for j in i:
+ curr_i = gcd(j, k)
+ ans += sum(
+ cnt for curr_j, cnt in gcds.items() if curr_i * curr_j % k == 0
+ )
+ gcds[curr_i] += 1
+ return ans
+
+
+if __name__ == "__main__":
+ obj = Solution()
+ print(obj.countPairs(nums=[3, 1, 2, 2, 2, 1, 3], k=2))
+ print(obj.countPairs(nums=[1, 2, 3, 4], k=1))
diff --git a/count_hidden_sequences.c b/count_hidden_sequences.c
new file mode 100644
index 0000000..0d8c2e1
--- /dev/null
+++ b/count_hidden_sequences.c
@@ -0,0 +1,29 @@
+// 2145. Count the Hidden Sequences
+#include "leetcode.h"
+
+/*
+ * you are given a 0-indexed array of 'n' integers 'differences', which
+ * describes the differences between each pair of consecutive integers of a
+ * hidden sequence of length '(n + 1)'. you are further given two integers
+ * 'lower' and 'upper' that describe the inclusive range of values '[lower,
+ * upper]' that the hidden sequence can contain. return the number of possible
+ * hidden sequences there are. if there are no possible sequences, return 0.
+ */
+
+int numberOfArrays(int *differences, int differencesSize, int lower,
+ int upper) {
+ long long cnt = 0, a = 0, b = 0;
+ for (int i = 0; i < differencesSize; i++) {
+ cnt += differences[i];
+ a = fmax(a, cnt);
+ b = fmin(b, cnt);
+ }
+ return fmax(0L, (upper - lower) - (a - b) + 1);
+}
+
+int main() {
+ int d1[] = {1, -3, 4}, d2[] = {3, -4, 5, 1, -2}, d3[] = {4, -7, 2};
+ printf("%d\n", numberOfArrays(d1, ARRAY_SIZE(d1), 1, 6)); // expect: 2
+ printf("%d\n", numberOfArrays(d2, ARRAY_SIZE(d2), -4, 5)); // expect: 4
+ printf("%d\n", numberOfArrays(d3, ARRAY_SIZE(d3), 3, 6)); // expect: 0
+}
diff --git a/count_hidden_sequences.py b/count_hidden_sequences.py
new file mode 100644
index 0000000..c229f7a
--- /dev/null
+++ b/count_hidden_sequences.py
@@ -0,0 +1,30 @@
+# 2145. Count the Hidden Sequences
+from itertools import accumulate
+
+"""
+you are given a 0-indexed array of 'n' integers 'differences', which
+describes the differences between each pair of consecutive integers of a
+hidden sequence of length '(n + 1)'. you are further given two integers
+'lower' and 'upper' that describe the inclusive range of values '[lower,
+upper]' that the hidden sequence can contain. return the number of possible
+hidden sequences there are. if there are no possible sequences, return 0.
+"""
+
+
+class Solution(object):
+ def numberOfcntrrays(self, differences, lower, upper):
+ """
+ :type differences: List[int]
+ :type lower: int
+ :type upper: int
+ :rtype: int
+ """
+ cnt = list(accumulate(differences, initial=0))
+ return max(0, (upper - lower) - (max(cnt) - min(cnt)) + 1)
+
+
+if __name__ == "__main__":
+ obj = Solution()
+ print(obj.numberOfcntrrays(differences=[1, -3, 4], lower=1, upper=6))
+ print(obj.numberOfcntrrays(differences=[3, -4, 5, 1, -2], lower=-4, upper=5))
+ print(obj.numberOfcntrrays(differences=[4, -7, 2], lower=3, upper=6))
diff --git a/count_num_fair_pairs.c b/count_num_fair_pairs.c
index 80d26f1..9ddfc9a 100644
--- a/count_num_fair_pairs.c
+++ b/count_num_fair_pairs.c
@@ -7,46 +7,25 @@
* i < j < n' and 'lower <= nums[i] + nums[j] <= upper'
*/
-int cmp(const void *a, const void *b) { return *(int *)a - *(int *)b; }
-
-int bs_lower(int *nums, int n, int left, int right, int lower) {
- int l = left, r = right;
- if (nums[r] < lower)
- return -1;
- while (l < r) {
- int m = l + (r - l) / 2;
- if (nums[m] < lower)
- l = m + 1;
- else
- r = m;
- }
- return l;
-}
-
-int bs_upper(int *nums, int n, int left, int right, int upper) {
- int l = left, r = right;
- if (nums[l] > upper)
- return -1;
- while (l < r) {
- int m = r - (r - l) / 2;
- if (nums[m] > upper)
- r = m - 1;
- else
- l = m;
- }
- return l;
+int cmp(const void *a, const void *b) {
+ return (*(int *)a > *(int *)b) - (*(int *)b > *(int *)a);
}
long long countFairPairs(int *nums, int numsSize, int lower, int upper) {
- int n = numsSize;
+ qsort(nums, numsSize, sizeof(int), cmp);
long long ans = 0;
- qsort(nums, n, sizeof(int), cmp);
- for (int i = 0; i < n - 1; i++) {
- int left = bs_lower(nums, n, i + 1, n - 1, lower - nums[i]);
- int right = bs_upper(nums, n, i + 1, n - 1, upper - nums[i]);
- if (left != -1 && right != -1)
- ans += right - left + 1;
- }
+ int i = 0, j = numsSize - 1;
+ while (i < j)
+ if (nums[i] + nums[j] < lower)
+ ans -= j - i++;
+ else
+ j--;
+ i = 0, j = numsSize - 1;
+ while (i < j)
+ if (nums[i] + nums[j] <= upper)
+ ans += j - i++;
+ else
+ j--;
return ans;
}
diff --git a/count_num_fair_pairs.py b/count_num_fair_pairs.py
index 5933dbd..8d02562 100644
--- a/count_num_fair_pairs.py
+++ b/count_num_fair_pairs.py
@@ -19,9 +19,8 @@ class Solution(object):
nums.sort()
ans = 0
for i in range(len(nums) - 1, -1, -1):
- v = nums[i]
- a = bisect.bisect_left(nums, lower - v, lo=0, hi=i)
- b = bisect.bisect_right(nums, upper - v, lo=0, hi=i)
+ a = bisect.bisect_left(nums, lower - nums[i], i + 1)
+ b = bisect.bisect_right(nums, upper - nums[i], i + 1)
ans += b - a
return ans
diff --git a/count_num_good_subarr.c b/count_num_good_subarr.c
new file mode 100644
index 0000000..40c20c4
--- /dev/null
+++ b/count_num_good_subarr.c
@@ -0,0 +1,94 @@
+// 2537. Count the Number of Good Subarrays
+#include "leetcode.h"
+
+/*
+ * given an integer array 'nums' and an integer 'k', return the number of good
+ * subarrays of 'nums'. a subarray 'arr' is good if there are at least 'k' pairs
+ * of indices '(i, j)' such that 'i < j' and 'arr[i] == arr[j]'. a subarray is a
+ * contiguous non-empty sequence of elements within an array.
+ */
+
+struct hash {
+ int *key;
+ int *val;
+ int size;
+};
+
+bool is_prime(int n) {
+ for (int i = 2; i < (int)sqrt(n) + 1; i++)
+ if (!(n % i))
+ return false;
+ return true;
+}
+
+struct hash *hash_init(int size) {
+ int max;
+ if (size < 8)
+ max = 11;
+ else {
+ max = size * 4 / 3;
+ int remove = (max - 3) % 4;
+ max += (remove > 0) * (4 - remove);
+ while (!is_prime(max))
+ max += 4;
+ }
+ struct hash *new = (struct hash *)malloc(sizeof(struct hash));
+ *new = (struct hash){(int *)calloc(max, sizeof(int)),
+ (int *)calloc(max, sizeof(int)), max};
+ return new;
+}
+
+void hash_free(struct hash *obj) {
+ free(obj->key);
+ free(obj->val);
+ free(obj);
+}
+
+int hash_getidx(struct hash *obj, int key) {
+ int idx = key % obj->size;
+ while (obj->key[idx] > 0 && obj->key[idx] != key)
+ if (++idx == obj->size)
+ idx = 0;
+ obj->key[idx] = key;
+ return idx;
+}
+
+int hash_getkey(struct hash *obj, int key) {
+ int idx = key % obj->size;
+ while (obj->key[idx] > 0) {
+ if (obj->key[idx] == key)
+ return idx;
+ if (++idx == obj->size)
+ idx = 0;
+ }
+ return -1;
+}
+
+int hash_addkey(struct hash *obj, int key) { return hash_getidx(obj, key); }
+
+long long countGood(int *nums, int numsSize, int k) {
+ long long ans = 0;
+ int curr = 0;
+ struct hash *map = hash_init(numsSize);
+ for (int l = 0, r = 0; r < numsSize; r++) {
+ int i = hash_getkey(map, nums[r]);
+ if (i == -1) {
+ i = hash_addkey(map, nums[r]);
+ map->val[i] = 1;
+ } else
+ curr += map->val[i]++;
+ while (curr >= k) {
+ ans += numsSize - r;
+ curr -= --map->val[hash_getidx(map, nums[l])];
+ l++;
+ }
+ }
+ hash_free(map);
+ return ans;
+}
+
+int main() {
+ int n1[] = {1, 1, 1, 1, 1}, n2[] = {3, 1, 4, 3, 2, 2, 4};
+ printf("%lld\n", countGood(n1, ARRAY_SIZE(n1), 10)); // expect: 1
+ printf("%lld\n", countGood(n2, ARRAY_SIZE(n2), 2)); // expect: 4
+}
diff --git a/count_num_good_subarr.py b/count_num_good_subarr.py
new file mode 100644
index 0000000..69eedce
--- /dev/null
+++ b/count_num_good_subarr.py
@@ -0,0 +1,35 @@
+# 2537. Count the Number of Good Subarrays
+from collections import Counter
+
+"""
+given an integer array 'nums' and an integer 'k', return the number of good
+subarrays of 'nums'. a subarray 'arr' is good if there are at least 'k' pairs
+of indices '(i, j)' such that 'i < j' and 'arr[i] == arr[j]'. a subarray is a
+contiguous non-empty sequence of elements within an array.
+"""
+
+
+class Solution(object):
+ def countGood(self, nums, k):
+ """
+ :type nums: List[int]
+ :type k: int
+ :rtype: int
+ """
+ ans, i = 0, 0
+ cnt = Counter()
+ for j in range(len(nums)):
+ k -= cnt[nums[j]]
+ cnt[nums[j]] += 1
+ while k <= 0:
+ cnt[nums[i]] -= 1
+ k += cnt[nums[i]]
+ i += 1
+ ans += i
+ return ans
+
+
+if __name__ == "__main__":
+ obj = Solution()
+ print(obj.countGood(nums=[1, 1, 1, 1, 1], k=10))
+ print(obj.countGood(nums=[3, 1, 4, 3, 2, 2, 4], k=2))
diff --git a/count_num_ideal_arr.c b/count_num_ideal_arr.c
new file mode 100644
index 0000000..298b1da
--- /dev/null
+++ b/count_num_ideal_arr.c
@@ -0,0 +1,36 @@
+// 2338. Count the Number of Ideal Arrays
+#include "leetcode.h"
+
+/*
+ * you are given two integers 'n' and 'maxValue' which are used to describe an
+ * ideal array. a 0-indexed integer array 'arr' of length 'n' is considered
+ * ideal if the following conditions hold true: every 'arr[i]' is a value from 1
+ * to 'maxValue' for '0 <= i < n', and every 'arr[i]' is divisble by 'arr[i -
+ * 1]'. return the number of distinct ideal arrays of length 'n'. since the
+ * answer may be very large, return it modulo 10^9+7.
+ */
+
+int idealArrays(int n, int maxValue) {
+ int cmb[10001][14] = {1}, cnt[10001][14] = {}, mod = 1e9 + 7;
+ if (!cmb[1][1]) {
+ for (int i = 1; i <= 10000; ++i)
+ for (int j = 0; j < 14; ++j)
+ cmb[i][j] = !j ? 1 : (cmb[i - 1][j - 1] + cmb[i - 1][j]) % mod;
+ for (int i = 1; i <= 10000; ++i) {
+ ++cnt[i][0];
+ for (int j = 2 * i; j <= 10000; j += i)
+ for (int k = 0; cnt[i][k]; ++k)
+ cnt[j][k + 1] += cnt[i][k];
+ }
+ }
+ int ans = 0;
+ for (int i = 1; i <= maxValue; ++i)
+ for (int j = 0; j < fmin(14, n) && cnt[i][j]; ++j)
+ ans = (1LL * cnt[i][j] * cmb[n - 1][j] + ans) % mod;
+ return ans;
+}
+
+int main() {
+ printf("%d\n", idealArrays(2, 5)); // expect: 10
+ printf("%d\n", idealArrays(5, 3)); // expect: 11
+}
diff --git a/count_num_ideal_arr.py b/count_num_ideal_arr.py
new file mode 100644
index 0000000..6966711
--- /dev/null
+++ b/count_num_ideal_arr.py
@@ -0,0 +1,38 @@
+# 2338. Count the Number of Ideal Arrays
+from collections import Counter
+from math import comb
+
+"""
+you are given two integers 'n' and 'maxValue' which are used to describe an
+ideal array. a 0-indexed integer array 'arr' of length 'n' is considered
+ideal if the following conditions hold true: every 'arr[i]' is a value from 1
+to 'maxValue' for '0 <= i < n', and every 'arr[i]' is divisble by 'arr[i -
+1]'. return the number of distinct ideal arrays of length 'n'. since the
+answer may be very large, return it modulo 10^9+7.
+"""
+
+
+class Solution(object):
+ def idealArrays(self, n, maxValue):
+ """
+ :type n: int
+ :type maxValue: int
+ :rtype: int
+ """
+ ans = maxValue
+ freq = {i: 1 for i in range(1, maxValue + 1)}
+ for i in range(1, n):
+ tmp = Counter()
+ for j in freq:
+ for k in range(2, maxValue // j + 1):
+ ans += comb(n - 1, i) * freq[j]
+ tmp[k * j] += freq[j]
+ freq = tmp
+ ans %= 10**9 + 7
+ return ans
+
+
+if __name__ == "__main__":
+ obj = Solution()
+ print(obj.idealArrays(n=2, maxValue=5))
+ print(obj.idealArrays(n=5, maxValue=3))
diff --git a/max_product_len_palindrome_subseq.c b/max_product_len_palindrome_subseq.c
new file mode 100644
index 0000000..b3e3a66
--- /dev/null
+++ b/max_product_len_palindrome_subseq.c
@@ -0,0 +1,46 @@
+// 2002. Maximum Product of the Length of Two Palindromic Subsequences
+#include "leetcode.h"
+
+/*
+ * given a string 's', find two disjoint palindromic subsequences of 's' such
+ * that the product of their lengths is maximised. the two subsequences are
+ * disjoint if they do not both pick a character at the same index. return the
+ * maximum possible product of the lengths of the two palindromic subsequences.
+ * a subsequence is a string that can be derived from another string by deleting
+ * some or none of its characters without changing the ordering of the remaining
+ * characters. a string is palindromic if it reads the same forward and backward
+ */
+
+int maxProduct(char *s) {
+ int n = strlen(s), *bits = (int *)calloc(1 << n, sizeof(int));
+ for (int i = 1; i < 1 << n; i++)
+ bits[i] = bits[i >> 1] + (i & 1);
+ for (int i = (1 << n) - 1; i >= 0; i--) {
+ int l = 0, r = n - 1;
+ while (l < r) {
+ while (l < n && !(i & (1 << l)))
+ l++;
+ while (r >= 0 && !(i & (1 << r)))
+ r--;
+ if (l < r && s[l] != s[r]) {
+ bits[i] = 0;
+ break;
+ }
+ l++, r--;
+ }
+ }
+ int ans = 1;
+ for (int i = (1 << n) - 1; i > 0; i--)
+ if (bits[i])
+ for (int j = (i + 1) & ~i; j < 1 << n; j = ((j | i) + 1) & ~i)
+ if (bits[j])
+ ans = fmax(ans, bits[i] * bits[j]);
+ return ans;
+}
+
+int main() {
+ char *s1 = "leetcodecom", *s2 = "bb", *s3 = "accbcaxxcxx";
+ printf("%d\n", maxProduct(s1)); // expect: 9
+ printf("%d\n", maxProduct(s2)); // expect: 1
+ printf("%d\n", maxProduct(s3)); // expect: 25
+}
diff --git a/max_product_len_palindrome_subseq.py b/max_product_len_palindrome_subseq.py
new file mode 100644
index 0000000..52ecafc
--- /dev/null
+++ b/max_product_len_palindrome_subseq.py
@@ -0,0 +1,46 @@
+# 2002. Maximum Product of the Length of Two Palindromic Subsequences
+
+"""
+given a string 's', find two disjoint palindromic subsequences of 's' such
+that the product of their lengths is maximised. the two subsequences are
+disjoint if they do not both pick a character at the same index. return the
+maximum possible product of the lengths of the two palindromic subsequences.
+a subsequence is a string that can be derived from another string by deleting
+some or none of its characters without changing the ordering of the remaining
+characters. a string is palindromic if it reads the same forward and backward
+"""
+
+
+class Solution(object):
+ def maxProduct(self, s):
+ """
+ :type s: str
+ :rtype: int
+ """
+ n = len(s)
+ first, last = [0] * (1 << n), [0] * (1 << n)
+ for i in range(n):
+ for j in range(1 << i, 1 << (i + 1)):
+ first[j] = i
+ for i in range(n):
+ for j in range(1 << i, 1 << n, 1 << (i + 1)):
+ last[j] = i
+
+ def dp(m):
+ if m & (m - 1) == 0:
+ return m != 0
+ f, l = first[m], last[m]
+ fb, lb = 1 << f, 1 << l
+ return max(dp(m - lb), dp(m - fb), dp(m - lb - fb) + (s[l] == s[f]) * 2)
+
+ ans = 0
+ for i in range(1, 1 << n):
+ ans = max(ans, dp(i) * dp((1 << n) - 1 - i))
+ return ans
+
+
+if __name__ == "__main__":
+ obj = Solution()
+ print(obj.maxProduct(s="leetcodecom"))
+ print(obj.maxProduct(s="bb"))
+ print(obj.maxProduct(s="accbcaxxcxx"))
diff --git a/rabbits_in_forest.c b/rabbits_in_forest.c
new file mode 100644
index 0000000..caf618f
--- /dev/null
+++ b/rabbits_in_forest.c
@@ -0,0 +1,36 @@
+// 781. Rabbits in Forest
+#include "leetcode.h"
+
+/*
+ * there is a forest with an unknown number of rabbits. we asked 'n' rabbits
+ * "how many rabbithave the same colour as you?" and collected the answers in an
+ * integer array 'answers' where 'answers[i]' is the answer of the i'th rabbit.
+ * given the array 'answers', return the minimum number of rabbits that could be
+ * in the forest.
+ */
+
+int numRabbits(int *answers, int answersSize) {
+ int ans = 0;
+ for (int i = 0; i < answersSize - 1; i++) {
+ int freq = 0;
+ if (answers[i] != -1 && answers[i])
+ for (int j = i + 1; j < answersSize; j++) {
+ if (answers[i] == answers[j]) {
+ answers[j] = -1;
+ freq++;
+ }
+ if (freq == answers[i])
+ break;
+ }
+ }
+ for (int i = 0; i < answersSize; i++)
+ if (answers[i] != -1)
+ ans += (answers[i] + 1);
+ return ans;
+}
+
+int main() {
+ int a1[] = {1, 1, 2}, a2[] = {10, 10, 10};
+ printf("%d\n", numRabbits(a1, ARRAY_SIZE(a1))); // expect: 5
+ printf("%d\n", numRabbits(a2, ARRAY_SIZE(a2))); // expect: 11
+}
diff --git a/rabbits_in_forest.py b/rabbits_in_forest.py
new file mode 100644
index 0000000..7d91e99
--- /dev/null
+++ b/rabbits_in_forest.py
@@ -0,0 +1,30 @@
+# 781. Rabbits in Forest
+from collections import Counter
+
+"""
+there is a forest with an unknown number of rabbits. we asked 'n' rabbits
+"how many rabbithave the same colour as you?" and collected the answers in an
+integer array 'answers' where 'answers[i]' is the answer of the i'th rabbit.
+given the array 'answers', return the minimum number of rabbits that could be
+in the forest.
+"""
+
+
+class Solution(object):
+ def numRabbits(self, answers):
+ """
+ :type answers: List[int]
+ :rtype: int
+ """
+ ans, freq = 0, Counter()
+ for i in answers:
+ if freq[i] % (i + 1) == 0:
+ ans += i + 1
+ freq[i] += 1
+ return ans
+
+
+if __name__ == "__main__":
+ obj = Solution()
+ print(obj.numRabbits(answers=[1, 1, 2]))
+ print(obj.numRabbits(answers=[10, 10, 10]))
diff --git a/substring_xor_queries.c b/substring_xor_queries.c
new file mode 100644
index 0000000..4c2a6d2
--- /dev/null
+++ b/substring_xor_queries.c
@@ -0,0 +1,137 @@
+// 2564. Substring XOR Queries
+#include "leetcode.h"
+
+/*
+ * you are given a binary string 's' and a 2d integer array 'queries' where
+ * 'queries[i] = [first_i, second_i]'. for the i'th query, find the shortest
+ * substring of 's' whose decimal value 'val' yields 'second_i' when bitwise
+ * xor'd with 'first_i'. in other words, 'val ^ first_i == second_i'. the answer
+ * to the i'th query is the endpoints of the substring '[left_i, right_i]' or
+ * '[-1, -1]' if no such substring exists. if there are multiple answers, choose
+ * the one with the minimum 'left_i'. return an array 'ans' where 'ans[i] =
+ * [left_i, right_i]' is the answer to the i'th query. a substring is a
+ * contiguous non-empty sequence of characters within a string.
+ */
+
+struct hash {
+ int key;
+ struct hash *next;
+ UT_hash_handle hh;
+};
+
+void resp(struct hash *entry, int idx, struct hash *entries, int **out) {
+ int start = idx, end = idx, target = entry->key;
+ while (target >>= 1)
+ --start;
+ do {
+ int res = entry - entries;
+ out[res][0] = start;
+ out[res][1] = end;
+ } while ((entry = entry->next));
+}
+
+int **substringXorQueries(char *s, int **queries, int queriesSize,
+ int *queriesColSize, int *returnSize,
+ int **returnColumnSizes) {
+ int **ans = (int **)malloc(queriesSize * sizeof(int *));
+ *returnColumnSizes = (int *)malloc(queriesSize * sizeof(int));
+ for (int i = 0; i < queriesSize; ++i) {
+ ans[i] = (int *)malloc(2 * sizeof(int));
+ (*returnColumnSizes)[i] = 2;
+ }
+ *returnSize = queriesSize;
+ struct hash *table = NULL, *entry;
+ struct hash *const entries =
+ (struct hash *)malloc(queriesSize * sizeof(struct hash));
+ for (int i = 0; i < queriesSize; ++i) {
+ int target = queries[i][0] ^ queries[i][1];
+ HASH_FIND_INT(table, &target, entry);
+ if (!entry) {
+ entries[i].key = target;
+ entries[i].next = NULL;
+ HASH_ADD_INT(table, key, &entries[i]);
+ } else {
+ entries[i].next = entry->next;
+ entry->next = &entries[i];
+ }
+ }
+ int arr[31], cnt = 0;
+ for (int i = 0; s[i]; i++) {
+ cnt = 30 == cnt ? 30 : cnt + 1;
+ for (int j = cnt - 1; j; --j) {
+ arr[j] = (arr[j - 1] << 1) + ('1' == s[i]);
+ HASH_FIND_INT(table, &arr[j], entry);
+ if (entry) {
+ resp(entry, i, entries, ans);
+ HASH_DEL(table, entry);
+ }
+ }
+ arr[0] = ('1' == s[i]);
+ HASH_FIND_INT(table, &arr[0], entry);
+ if (entry) {
+ resp(entry, i, entries, ans);
+ HASH_DEL(table, entry);
+ }
+ }
+ struct hash *tmp;
+ HASH_ITER(hh, table, entry, tmp) {
+ do {
+ ans[entry - entries][0] = -1;
+ ans[entry - entries][1] = -1;
+ } while ((entry = entry->next));
+ }
+ HASH_CLEAR(hh, table);
+ free(entries);
+ return ans;
+}
+
+int main() {
+ char *s1 = "101101", *s2 = "0101", *s3 = "1";
+ int q1i[2][2] = {{0, 5}, {1, 2}}, q2i[1][2] = {{12, 8}}, q3i[1][2] = {{4, 5}};
+ struct two_d_arr q1, q2, q3;
+ two_d_arr_init(&q1, ARRAY_SIZE(q1i), ARRAY_SIZE(q1i[0]), q1i);
+ two_d_arr_init(&q2, ARRAY_SIZE(q2i), ARRAY_SIZE(q2i[0]), q2i);
+ two_d_arr_init(&q3, ARRAY_SIZE(q3i), ARRAY_SIZE(q3i[0]), q3i);
+ int rs1, *rcs1,
+ **sxq1 = substringXorQueries(s1, q1.arr, q1.row_size, q1.col_size, &rs1,
+ &rcs1);
+ int rs2, *rcs2,
+ **sxq2 = substringXorQueries(s2, q2.arr, q2.row_size, q2.col_size, &rs2,
+ &rcs2);
+ int rs3, *rcs3,
+ **sxq3 = substringXorQueries(s3, q3.arr, q3.row_size, q3.col_size, &rs3,
+ &rcs3);
+ for (int i = 0; i < rs1; i++) {
+ for (int j = 0; j < rcs1[i]; j++)
+ printf("%d ", sxq1[i][j]); // expect: [[0,2],[2,3]]
+ printf("\n");
+ }
+ printf("\n");
+ for (int i = 0; i < rs2; i++) {
+ for (int j = 0; j < rcs2[i]; j++)
+ printf("%d ", sxq2[i][j]); // expect: [[-1,-1]]
+ printf("\n");
+ }
+ printf("\n");
+ for (int i = 0; i < rs3; i++) {
+ for (int j = 0; j < rcs3[i]; j++)
+ printf("%d ", sxq1[i][j]); // expect: [[0,0]]
+ printf("\n");
+ }
+ printf("\n");
+ for (int i = 0; i < rs1; i++)
+ free(sxq1[i]);
+ free(sxq1);
+ for (int i = 0; i < rs2; i++)
+ free(sxq2[i]);
+ free(sxq1);
+ for (int i = 0; i < rs3; i++)
+ free(sxq3[i]);
+ free(sxq3);
+ free(rcs1);
+ free(rcs2);
+ free(rcs3);
+ two_d_arr_free(&q1);
+ two_d_arr_free(&q2);
+ two_d_arr_free(&q3);
+}
diff --git a/substring_xor_queries.py b/substring_xor_queries.py
new file mode 100644
index 0000000..4e40a1c
--- /dev/null
+++ b/substring_xor_queries.py
@@ -0,0 +1,43 @@
+# 2564. Substring XOR Queries
+from collections import defaultdict
+
+"""
+you are given a binary string 's' and a 2d integer array 'queries' where
+'queries[i] = [first_i, second_i]'. for the i'th query, find the shortest
+substring of 's' whose decimal value 'val' yields 'second_i' when bitwise
+xor'd with 'first_i'. in other words, 'val ^ first_i == second_i'. the answer
+to the i'th query is the endpoints of the substring '[left_i, right_i]' or
+'[-1, -1]' if no such substring exists. if there are multiple answers, choose
+the one with the minimum 'left_i'. return an array 'ans' where 'ans[i] =
+[left_i, right_i]' is the answer to the i'th query. a substring is a
+contiguous non-empty sequence of characters within a string.
+"""
+
+
+class Solution(object):
+ def substringXorQueries(self, s, queries):
+ """
+ :type s: str
+ :type queries: List[List[int]]
+ :rtype: List[List[int]]
+ """
+ n = len(s)
+ vis = defaultdict(lambda: [-1, -1])
+ for i in range(n - 1, -1, -1):
+ if s[i] == "0":
+ vis[0] = [i, i]
+ continue
+ curr = 0
+ for j in range(i, n):
+ curr = curr * 2 + int(s[j])
+ if curr > 2**32:
+ break
+ vis[curr] = [i, j]
+ return [vis[a ^ b] for b, a in queries]
+
+
+if __name__ == "__main__":
+ obj = Solution()
+ print(obj.substringXorQueries(s="101101", queries=[[0, 5], [1, 2]]))
+ print(obj.substringXorQueries(s="0101", queries=[[12, 8]]))
+ print(obj.substringXorQueries(s="1", queries=[[4, 5]]))