diff options
-rw-r--r-- | lex_smallest_beaut_str.c | 47 | ||||
-rw-r--r-- | lex_smallest_beaut_str.py | 36 | ||||
-rw-r--r-- | max_diff_between_adj_elem.c | 23 | ||||
-rw-r--r-- | max_diff_between_adj_elem.py | 27 | ||||
-rw-r--r-- | max_diff_even_odd_freq2.c | 120 | ||||
-rw-r--r-- | max_diff_even_odd_freq2.py | 78 | ||||
-rw-r--r-- | max_diff_remap_digit.c | 30 | ||||
-rw-r--r-- | max_diff_remap_digit.py | 26 | ||||
-rw-r--r-- | min_max_diff_pair.c | 18 | ||||
-rw-r--r-- | min_max_diff_pair.py | 42 |
10 files changed, 437 insertions, 10 deletions
diff --git a/lex_smallest_beaut_str.c b/lex_smallest_beaut_str.c new file mode 100644 index 0000000..8009a4a --- /dev/null +++ b/lex_smallest_beaut_str.c @@ -0,0 +1,47 @@ +// 2663. Lexicographically Smallest Beautiful String +#include "leetcode.h" + +/* + * a string is beautiful if it consists of the first 'k' letters of the english + * lowercase alphabet, it does not contain a palindrome of length 2 or more + * which is a palindrome. you are given a beautiful string 's' of length 'n', + * and a positive integer 'k'. return the lexicographically smallest string of + * length 'n' which is larger than 's', and is beautiful. if there is no such + * string, return an empty string. + */ + +char *smallestBeautifulString(char *s, int k) { + int n = strlen(s); + char *ans = (char *)malloc((n + 1) * sizeof(char)); + strcpy(ans, s); + for (int i = n - 1; i >= 0; i--) { + for (int j = ans[i] - 'a' + 1; j < k; j++) { + char curr = j + 'a'; + if ((i < 1 || curr != ans[i - 1]) && (i < 2 || curr != ans[i - 2])) { + ans[i] = curr; + for (int l = i + 1; l < n; l++) { + for (int m = 0; m < k; m++) { + curr = m + 'a'; + if ((l < 1 || curr != ans[l - 1]) && + (l < 2 || curr != ans[l - 2])) { + ans[l] = curr; + break; + } + } + } + return ans; + } + } + } + return ""; +} + +int main() { + char *s1 = "abcz", *s2 = "dc"; + char *sbs1 = smallestBeautifulString(s1, 26); + char *sbs2 = smallestBeautifulString(s2, 4); + printf("%s\n", sbs1); // expect: abda + printf("%s\n", sbs2); // expect: null + free(sbs1); + free(sbs2); +} diff --git a/lex_smallest_beaut_str.py b/lex_smallest_beaut_str.py new file mode 100644 index 0000000..58e1381 --- /dev/null +++ b/lex_smallest_beaut_str.py @@ -0,0 +1,36 @@ +# 2663. Lexicographically Smallest Beautiful String + +""" +a string is beautiful if it consists of the first 'k' letters of the english +lowercase alphabet, it does not contain a palindrome of length 2 or more +which is a palindrome. you are given a beautiful string 's' of length 'n', +and a positive integer 'k'. return the lexicographically smallest string of +length 'n' which is larger than 's', and is beautiful. if there is no such +string, return an empty string. +""" + + +class Solution(object): + def smallestBeautifulString(self, s, k): + """ + :type s: str + :type k: int + :rtype: str + """ + ans = [ord(c) - ord("a") for c in s] + n = len(ans) - 1 + while n >= 0: + ans[n] += 1 + if ans[n] == k: + n -= 1 + elif ans[n] not in ans[max(n - 2, 0) : n]: + for j in range(n + 1, len(ans)): + ans[j] = min({0, 1, 2} - set(ans[max(0, j - 2) : j])) + return "".join(chr(ord("a") + i) for i in ans) + return "" + + +if __name__ == "__main__": + obj = Solution() + print(obj.smallestBeautifulString(s="abcz", k=26)) + print(obj.smallestBeautifulString(s="dc", k=4)) diff --git a/max_diff_between_adj_elem.c b/max_diff_between_adj_elem.c new file mode 100644 index 0000000..a96f02c --- /dev/null +++ b/max_diff_between_adj_elem.c @@ -0,0 +1,23 @@ +// 3423. Maximum Difference Between Adjacent Elements in a Circular Array +#include "leetcode.h" + +/* + * given a circular array 'nums', find the maximum absolute difference between + * adjacent elements. note, in a circular array, the first and last elements are + * adjacent. + */ + +int maxAdjacentDistance(int *nums, int numsSize) { + int ans = abs(nums[0] - nums[numsSize - 1]); + for (int i = 1; i < numsSize; i++) { + int curr = abs(nums[i - 1] - nums[i]); + ans = fmax(ans, curr); + } + return ans; +} + +int main() { + int n1[] = {1, 2, 4}, n2[] = {-5, -10, -5}; + printf("%d\n", maxAdjacentDistance(n1, ARRAY_SIZE(n2))); // expect: 3 + printf("%d\n", maxAdjacentDistance(n1, ARRAY_SIZE(n2))); // expect: 5 +} diff --git a/max_diff_between_adj_elem.py b/max_diff_between_adj_elem.py new file mode 100644 index 0000000..4334537 --- /dev/null +++ b/max_diff_between_adj_elem.py @@ -0,0 +1,27 @@ +# 3423. Maximum Difference Between Adjacent Elements in a Circular Array + +""" +given a circular array 'nums', find the maximum absolute difference between +adjacent elements. note, in a circular array, the first and last elements are +adjacent. +""" + + +class Solution(object): + def maxAdjacentDistance(self, nums): + """ + :type nums: List[int] + :rtype: int + """ + n = len(nums) + ans = abs(nums[0] - nums[n - 1]) + for i in range(1, n): + curr = abs(nums[i - 1] - nums[i]) + ans = max(ans, curr) + return ans + + +if __name__ == "__main__": + obj = Solution() + print(obj.maxAdjacentDistance(nums=[1, 2, 4])) + print(obj.maxAdjacentDistance(nums=[-5, -10, -5])) diff --git a/max_diff_even_odd_freq2.c b/max_diff_even_odd_freq2.c new file mode 100644 index 0000000..8d32226 --- /dev/null +++ b/max_diff_even_odd_freq2.c @@ -0,0 +1,120 @@ +// 3445. Maximum Difference Between Even and Odd Frequency II +#include "leetcode.h" + +/* + * you are given a string 's' and an integer 'k'. your task is to find the + * maximum difference between the frequency of two characters 'freq[a], - + * freq[b]', in a substring 'subs' of 's' such that 'subs' has a size of at + * least 'k', character 'a' has an odd frequency in 'subs', character 'b' has an + * even frequency in 'subs'. return the maximum difference. note that 'subs' can + * contain more than 2 distinct characters. + */ + +static int upper_bound(const int *arr, int n, int key) { + int low = 0, high = n; + while (low < high) { + int mid = low + ((high - low) >> 1); + if (arr[mid] <= key) + low = mid + 1; + else + high = mid; + } + return low; +} + +int maxDifference(char *s, int k) { + int n = strlen(s); + if (!n || k > n) + return -1; + int (*freq)[5] = malloc(sizeof(int[5]) * n), present[5] = {0}; + if (!freq) + return -1; + for (int i = 0; i < n; i++) { + int c = s[i] - '0'; + if (!i) + memset(freq[i], 0, sizeof(int) * 5); + else + memcpy(freq[i], freq[i - 1], sizeof(int) * 5); + freq[i][c]++; + present[c] = 1; + } + int ans = INT_MIN; + for (int a = 0; a < 5; a++) { + if (!present[a]) + continue; + for (int b = 0; b < 5; b++) { + if (!present[b] || a == b) + continue; + int *idx_list[4], *val_list[4], size[4]; + for (int i = 0; i < 4; i++) { + idx_list[i] = (int *)malloc(sizeof(int) * n); + val_list[i] = (int *)malloc(sizeof(int) * n); + size[i] = 0; + } + int odd = 0, even = 0; + for (int i = 0; i < n; i++) { + int c = s[i] - '0'; + if (c == a) + odd++; + else if (c == b) + even++; + if ((odd & 1) && (even & 1) == 0 && (i + 1) >= k && even > 0) { + int diff = odd - even; + if (diff > ans) + ans = diff; + } + int key1 = ((odd % 2 == 0) ? 1 : 0) << 1 | ((even % 2 == 0) ? 0 : 1); + if (size[key1] > 0) { + int limit = i - k; + if (limit >= 0) { + int pos = upper_bound(idx_list[key1], size[key1], limit); + if (pos > 0) { + int prev = pos - 1, l = 0, r = prev, curr_min = INT_MAX; + while (l <= r) { + int mid = (l + r) >> 1, j = idx_list[key1][mid]; + if (freq[i][b] != freq[j][b]) { + int v = val_list[key1][mid]; + if (v < curr_min) + curr_min = v; + l = mid + 1; + } else + r = mid - 1; + } + if (curr_min != INT_MAX) { + int cur = odd - even - curr_min; + if (cur > ans) + ans = cur; + } + } + } + } + int key2 = (odd % 2) << 1 | (even % 2), curr_diff = odd - even; + if (!size[key2]) { + idx_list[key2][0] = i; + val_list[key2][0] = curr_diff; + size[key2] = 1; + } else { + int prev_min = val_list[key2][size[key2] - 1]; + int new_min = (prev_min < curr_diff) ? prev_min : curr_diff; + idx_list[key2][size[key2]] = i; + val_list[key2][size[key2]] = new_min; + size[key2]++; + } + } + for (int i = 0; i < 4; i++) { + free(idx_list[i]); + free(val_list[i]); + } + } + } + + free(freq); + return (ans == INT_MIN ? -1 : ans); +} + +int main() { + char *s1 = "12233", *s2 = "1122211", *s3 = "110"; + printf("%d\n", maxDifference(s1, 4)); // expect: -1 + printf("%d\n", maxDifference(s2, 3)); // expect: 1 + printf("%d\n", maxDifference(s3, 3)); // expect: -1 +} diff --git a/max_diff_even_odd_freq2.py b/max_diff_even_odd_freq2.py new file mode 100644 index 0000000..a24d3d0 --- /dev/null +++ b/max_diff_even_odd_freq2.py @@ -0,0 +1,78 @@ +# 3445. Maximum Difference Between Even and Odd Frequency II + +""" +you are given a string 's' and an integer 'k'. your task is to find the +maximum difference between the frequency of two characters 'freq[a], - +freq[b]', in a substring 'subs' of 's' such that 'subs' has a size of at +least 'k', character 'a' has an odd frequency in 'subs', character 'b' has an +even frequency in 'subs'. return the maximum difference. note that 'subs' can +contain more than 2 distinct characters. +""" + + +class fenwick_tree: + inf = float("inf") + + def __init__(self, n): + self.n = n + self.tree = [self.inf] * (n + 1) + + def update(self, i, val): + pos = i + 1 + while pos <= self.n: + self.tree[pos] = min(self.tree[pos], val) + pos += pos & -pos + + def query(self, i): + res, pos = self.inf, i + 1 + while pos > 0: + res = min(res, self.tree[pos]) + pos -= pos & -pos + return res + + +class Solution(object): + def maxDifference(self, s, k): + """ + :type s: str + :type k: int + :rtype: int + """ + n, ans = len(s), float("-inf") + for a in range(5): + for b in range(5): + if a == b: + continue + d = [0] * (n + 1) + pa, pb = [0] * (n + 1), [0] * (n + 1) + cnt_b = [0] * (n + 1) + for i in range(1, n + 1): + digit = int(s[i - 1]) + d[i] = ( + d[i - 1] + (1 if digit == a else 0) - (1 if digit == b else 0) + ) + pa[i] = (pa[i - 1] + (1 if digit == a else 0)) & 1 + pb[i] = (pb[i - 1] + (1 if digit == b else 0)) & 1 + cnt_b[i] = cnt_b[i - 1] + (1 if digit == b else 0) + trees = [[fenwick_tree(n + 1) for _ in range(2)] for _ in range(2)] + for j in range(n + 1): + if j >= k: + idx = j - k + trees[pa[idx]][pb[idx]].update(cnt_b[idx], d[idx]) + if j > 0: + need_p, need_q = ( + 1 - pa[j], + pb[j], + ) + if cnt_b[j] > 0: + best = trees[need_p][need_q].query(cnt_b[j] - 1) + if best != fenwick_tree.inf: + ans = max(ans, d[j] - best) + return ans + + +if __name__ == "__main__": + obj = Solution() + print(obj.maxDifference(s="12233", k=4)) + print(obj.maxDifference(s="1122211", k=3)) + print(obj.maxDifference(s="110", k=3)) diff --git a/max_diff_remap_digit.c b/max_diff_remap_digit.c new file mode 100644 index 0000000..3eff54a --- /dev/null +++ b/max_diff_remap_digit.c @@ -0,0 +1,30 @@ +// 2566. Maximum Difference by Remapping a Digit +#include "leetcode.h" + +/* + * you are given an integer 'num'. you know that bob will sneakily remap one of + * the 10 possible digits to another digit. return the difference between the + * maximum and minimum values bob can make by remapping exactly one digit in + * nums. + */ + +int minMaxDifference(int num) { + int min = num, max = num; + for (int i = 0; i < 10; ++i) { + int low = 0, high = 0, mult = 1; + for (int j = num; j; j /= 10) { + bool replace = j % 10 == i; + low += (replace ? 0 : j % 10) * mult; + high += (replace ? 9 : j % 10) * mult; + mult *= 10; + } + min = fmin(min, low); + max = fmax(max, high); + } + return max - min; +} + +int main() { + printf("%d\n", minMaxDifference(11891)); // expect: 99009 + printf("%d\n", minMaxDifference(90)); // expect: 99 +} diff --git a/max_diff_remap_digit.py b/max_diff_remap_digit.py new file mode 100644 index 0000000..5d802ed --- /dev/null +++ b/max_diff_remap_digit.py @@ -0,0 +1,26 @@ +# 2566. Maximum Difference by Remapping a Digit + +""" +you are given an integer 'num'. you know that bob will sneakily remap one of +the 10 possible digits to another digit. return the difference between the +maximum and minimum values bob can make by remapping exactly one digit in +nums. +""" + + +class Solution(object): + def minMaxDifference(self, num): + """ + :type num: int + :rtype: int + """ + num, i = str(num), 0 + while num[i] == "9" and i < len(num) - 1: + i += 1 + return int(num.replace(num[i], "9")) - int(num.replace(num[0], "0")) + + +if __name__ == "__main__": + obj = Solution() + print(obj.minMaxDifference(num=11891)) + print(obj.minMaxDifference(num=90)) diff --git a/min_max_diff_pair.c b/min_max_diff_pair.c index 6172bc7..7577e3b 100644 --- a/min_max_diff_pair.c +++ b/min_max_diff_pair.c @@ -1,6 +1,5 @@ // 2616. Minimize the Maximum Difference of Pairs -#include <stdio.h> -#include <stdlib.h> +#include "leetcode.h" /* * given a 0-indexed integer array 'nums' and an integer 'p'. find 'p' pairs of @@ -14,13 +13,12 @@ int cmp(const void *a, const void *b) { return *(int *)a - *(int *)b; } -int minimizeMax(int *nums, int nums_size, int p) { - qsort(nums, nums_size, sizeof(int), cmp); - int i, j, left = 0, right = nums[nums_size - 1] - nums[0]; +int minimizeMax(int *nums, int numsSize, int p) { + qsort(nums, numsSize, sizeof(int), cmp); + int i, j, left = 0, right = nums[numsSize - 1] - nums[0]; while (left < right) { - int mid = (left + right) / 2; - int cnt = 0; - for (int i = 0; i + 1 < nums_size; ++i) + int mid = (left + right) / 2, cnt = 0; + for (int i = 0; i + 1 < numsSize; ++i) if (mid >= nums[i + 1] - nums[i]) ++cnt, ++i; if (cnt >= p) @@ -33,6 +31,6 @@ int minimizeMax(int *nums, int nums_size, int p) { int main() { int n1[] = {10, 1, 2, 7, 1, 3}, n2[] = {4, 2, 1, 2}; - printf("%d\n", minimizeMax(n1, 6, 2)); // expect: 1 - printf("%d\n", minimizeMax(n2, 4, 1)); // expect: 0 + printf("%d\n", minimizeMax(n1, ARRAY_SIZE(n1), 2)); // expect: 1 + printf("%d\n", minimizeMax(n2, ARRAY_SIZE(n2), 1)); // expect: 0 } diff --git a/min_max_diff_pair.py b/min_max_diff_pair.py new file mode 100644 index 0000000..8c5478d --- /dev/null +++ b/min_max_diff_pair.py @@ -0,0 +1,42 @@ +# 2616. Minimize the Maximum Difference of Pairs + +""" +given a 0-indexed integer array 'nums' and an integer 'p'. find 'p' pairs of +indices of 'nums' such that the maximum difference amongst all the pairs is +minimised. also, ensure no index appears more than once amongst that 'p' +pairs. note that for a pair of elements at the index 'i' and 'j'. the +difference of this pair is '|nums[i] - nums[j]|', where '|x|' represents the +absolute value of 'x'. return the minimum maximum difference among all 'p' +pairs. we define the maximum of an empty set to be zero. +""" + + +class Solution(object): + def minimizeMax(self, nums, p): + """ + :type nums: List[int] + :type p: int + :rtype: int + """ + nums.sort() + n = len(nums) + left, right = 0, nums[-1] - nums[0] + while left < right: + mid = (left + right) // 2 + i, j = 1, 0 + while i < n: + if nums[i] - nums[i - 1] <= mid: + i += 1 + j += 1 + i += 1 + if j >= p: + right = mid + else: + left = mid + 1 + return left + + +if __name__ == "__main__": + obj = Solution() + print(obj.minimizeMax(nums=[10, 1, 2, 7, 1, 3], p=2)) + print(obj.minimizeMax(nums=[4, 2, 1, 2], p=1)) |