# weekly-contest-291

## A

### Statement

`number`恰好 移除 一个 等于 `digit` 的字符后，找出并返回按 十进制 表示 最大 的结果字符串。生成的测试用例满足 `digit``number` 中出现至少一次。

``````输入：number = "123", digit = "3"

``````

``````输入：number = "1231", digit = "1"

``````

``````输入：number = "551", digit = "5"

``````

• `2 <= number.length <= 100`
• `number` 由数字 `'1'``'9'` 组成
• `digit``'1'``'9'` 中的一个数字
• `digit``number` 中出现至少一次

You are given a string `number` representing a positive integer and a character `digit`.

Return the resulting string after removing exactly one occurrence of `digit` from `number` such that the value of the resulting string in decimal form is maximized. The test cases are generated such that `digit` occurs at least once in `number`.

Example 1:

``````Input: number = "123", digit = "3"
Output: "12"
Explanation: There is only one '3' in "123". After removing '3', the result is "12".
``````

Example 2:

``````Input: number = "1231", digit = "1"
Output: "231"
Explanation: We can remove the first '1' to get "231" or remove the second '1' to get "123".
Since 231 > 123, we return "231".
``````

Example 3:

``````Input: number = "551", digit = "5"
Output: "51"
Explanation: We can remove either the first or second '5' from "551".
Both result in the string "51".
``````

Constraints:

• `2 <= number.length <= 100`
• `number` consists of digits from `'1'` to `'9'`.
• `digit` is a digit from `'1'` to `'9'`.
• `digit` occurs at least once in `number`.

### Solution

``````class Solution:
def removeDigit(self, s: str, digit: str) -> str:
cur_s = ""
res = 0
for i in range(len(s)):
if s[i] == digit:
cur_t = cur_s + s[i + 1:]
res = max(res, int(cur_t))
cur_s += s[i]
return str(res)
``````

## B

### Statement

``````输入：cards = [3,4,2,3,4,7]

``````输入：cards = [1,0,5,3]

• `1 <= cards.length <= 105`
• `0 <= cards[i] <= 106`

You are given an integer array `cards` where `cards[i]` represents the value of the `ith` card. A pair of cards are matching if the cards have the same value.

Return the minimum number of consecutive cards you have to pick up to have a pair of matching cards among the picked cards. If it is impossible to have matching cards, return `-1`.

Example 1:

``````Input: cards = [3,4,2,3,4,7]
Output: 4
Explanation: We can pick up the cards [3,4,2,3] which contain a matching pair of cards with value 3. Note that picking up the cards [4,2,3,4] is also optimal.
``````

Example 2:

``````Input: cards = [1,0,5,3]
Output: -1
Explanation: There is no way to pick up a set of consecutive cards that contain a pair of matching cards.
``````

Constraints:

• `1 <= cards.length <= 105`
• `0 <= cards[i] <= 106`

### Solution

``````#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

#define endl "\n"
#define fi first
#define se second
#define all(x) begin(x), end(x)
#define rall rbegin(a), rend(a)
#define bitcnt(x) (__builtin_popcountll(x))
#define complete_unique(a) a.erase(unique(begin(a), end(a)), end(a))
#define mst(x, a) memset(x, a, sizeof(x))
#define MP make_pair

using ll = long long;
using ull = unsigned long long;
using db = double;
using ld = long double;
using VLL = std::vector<ll>;
using VI = std::vector<int>;
using PII = std::pair<int, int>;
using PLL = std::pair<ll, ll>;

using namespace __gnu_pbds;
using namespace std;
template <typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

template <typename T, typename S>
inline bool chmax(T &a, const S &b) {
return a < b ? a = b, 1 : 0;
}

template <typename T, typename S>
inline bool chmin(T &a, const S &b) {
return a > b ? a = b, 1 : 0;
}

#ifdef LOCAL
#include <debug.hpp>
#else
#define dbg(...)
#endif

class Solution {
public:
int minimumCardPickup(vector<int> &cards) {
map<int, int> mp;
int n = static_cast<int>(cards.size());
int res = n + 1;
for (int i = 0; i < n; i++) {
int c = cards[i];
if (mp.count(c)) {
res = min<int>(res, i - mp[c] + 1);
}

mp[c] = i;
}

if (res == n + 1) {
res = -1;
}

return res;
}
};

#ifdef LOCAL

int main() {
return 0;
}

#endif
``````

## C

### Statement

• 两数组长度 不同 ，或者
• 存在 至少 一个下标 `i` 满足 `nums1[i] != nums2[i]`

``````输入：nums = [2,3,3,2,2], k = 2, p = 2

、[2,3]、[2,3,3]、[2,3,3,2]、、[3,3]、[3,3,2]、[3,3,2,2]、[3,2]、[3,2,2] 和 [2,2] 。

``````

``````输入：nums = [1,2,3,4], k = 4, p = 1

nums 中的所有元素都可以被 p = 1 整除。

``````

• `1 <= nums.length <= 200`
• `1 <= nums[i], p <= 200`
• `1 <= k <= nums.length`

Given an integer array `nums` and two integers `k` and `p`, return the number of distinct subarrays which have at most `k` elements divisible by `p`.

Two arrays `nums1` and `nums2` are said to be distinct if:

• They are of different lengths, or
• There exists at least one index `i` where `nums1[i] != nums2[i]`.

A subarray is defined as a non-empty contiguous sequence of elements in an array.

Example 1:

``````Input: nums = [2,3,3,2,2], k = 2, p = 2
Output: 11
Explanation:
The elements at indices 0, 3, and 4 are divisible by p = 2.
The 11 distinct subarrays which have at most k = 2 elements divisible by 2 are:
, [2,3], [2,3,3], [2,3,3,2], , [3,3], [3,3,2], [3,3,2,2], [3,2], [3,2,2], and [2,2].
Note that the subarrays  and  occur more than once in nums, but they should each be counted only once.
The subarray [2,3,3,2,2] should not be counted because it has 3 elements that are divisible by 2.
``````

Example 2:

``````Input: nums = [1,2,3,4], k = 4, p = 1
Output: 10
Explanation:
All element of nums are divisible by p = 1.
Also, every subarray of nums will have at most 4 elements that are divisible by 1.
Since all subarrays are distinct, the total number of subarrays satisfying all the constraints is 10.
``````

Constraints:

• `1 <= nums.length <= 200`
• `1 <= nums[i], p <= 200`
• `1 <= k <= nums.length`

### Solution

``````#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

#define endl "\n"
#define fi first
#define se second
#define all(x) begin(x), end(x)
#define rall rbegin(a), rend(a)
#define bitcnt(x) (__builtin_popcountll(x))
#define complete_unique(a) a.erase(unique(begin(a), end(a)), end(a))
#define mst(x, a) memset(x, a, sizeof(x))
#define MP make_pair

using ll = long long;
using ull = unsigned long long;
using db = double;
using ld = long double;
using VLL = std::vector<ll>;
using VI = std::vector<int>;
using PII = std::pair<int, int>;
using PLL = std::pair<ll, ll>;

using namespace __gnu_pbds;
using namespace std;
template <typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

template <typename T, typename S>
inline bool chmax(T &a, const S &b) {
return a < b ? a = b, 1 : 0;
}

template <typename T, typename S>
inline bool chmin(T &a, const S &b) {
return a > b ? a = b, 1 : 0;
}

#ifdef LOCAL
#include <debug.hpp>
#else
#define dbg(...)
#endif

class Solution {
public:
int countDistinct(vector<int> &nums, int k, int p) {
int n = static_cast<int>(nums.size());
int l = 0;
int cur = 0;
set<vector<int>> se;
for (int i = 0; i < n; i++) {
int x = nums[i];
if (x % p == 0) {
++cur;
}

while (cur > k) {
if (nums[l] % p == 0) {
--cur;
}

++l;
}

vector<int> v;
for (int j = i; j >= l; j--) {
v.push_back(nums[j]);
se.insert(v);
}
}

return se.size();
}
};

#ifdef LOCAL

int main() {
return 0;
}

#endif
``````

## D

### Statement

• 例如，`"abbca"` 的引力为 `3` ，因为其中有 `3` 个不同字符 `'a'``'b'``'c'`

``````输入：s = "abbca"

- 长度为 1 的子字符串："a"、"b"、"b"、"c"、"a" 的引力分别为 1、1、1、1、1，总和为 5 。
- 长度为 2 的子字符串："ab"、"bb"、"bc"、"ca" 的引力分别为 2、1、2、2 ，总和为 7 。
- 长度为 3 的子字符串："abb"、"bbc"、"bca" 的引力分别为 2、2、3 ，总和为 7 。
- 长度为 4 的子字符串："abbc"、"bbca" 的引力分别为 3、3 ，总和为 6 。
- 长度为 5 的子字符串："abbca" 的引力为 3 ，总和为 3 。

``````

``````输入：s = "code"

- 长度为 1 的子字符串："c"、"o"、"d"、"e" 的引力分别为 1、1、1、1 ，总和为 4 。
- 长度为 2 的子字符串："co"、"od"、"de" 的引力分别为 2、2、2 ，总和为 6 。
- 长度为 3 的子字符串："cod"、"ode" 的引力分别为 3、3 ，总和为 6 。
- 长度为 4 的子字符串："code" 的引力为 4 ，总和为 4 。

``````

• `1 <= s.length <= 105`
• `s` 由小写英文字母组成

The appeal of a string is the number of distinct characters found in the string.

• For example, the appeal of `"abbca"` is `3` because it has `3` distinct characters: `'a'`, `'b'`, and `'c'`.

Given a string `s`, return the total appeal of all of its substrings.

A substring is a contiguous sequence of characters within a string.

Example 1:

``````Input: s = "abbca"
Output: 28
Explanation: The following are the substrings of "abbca":
- Substrings of length 1: "a", "b", "b", "c", "a" have an appeal of 1, 1, 1, 1, and 1 respectively. The sum is 5.
- Substrings of length 2: "ab", "bb", "bc", "ca" have an appeal of 2, 1, 2, and 2 respectively. The sum is 7.
- Substrings of length 3: "abb", "bbc", "bca" have an appeal of 2, 2, and 3 respectively. The sum is 7.
- Substrings of length 4: "abbc", "bbca" have an appeal of 3 and 3 respectively. The sum is 6.
- Substrings of length 5: "abbca" has an appeal of 3. The sum is 3.
The total sum is 5 + 7 + 7 + 6 + 3 = 28.
``````

Example 2:

``````Input: s = "code"
Output: 20
Explanation: The following are the substrings of "code":
- Substrings of length 1: "c", "o", "d", "e" have an appeal of 1, 1, 1, and 1 respectively. The sum is 4.
- Substrings of length 2: "co", "od", "de" have an appeal of 2, 2, and 2 respectively. The sum is 6.
- Substrings of length 3: "cod", "ode" have an appeal of 3 and 3 respectively. The sum is 6.
- Substrings of length 4: "code" has an appeal of 4. The sum is 4.
The total sum is 4 + 6 + 6 + 4 = 20.
``````

Constraints:

• `1 <= s.length <= 105`
• `s` consists of lowercase English letters.

### Solution

``````#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <vector>

#define endl "\n"
#define fi first
#define se second
#define all(x) begin(x), end(x)
#define rall rbegin(a), rend(a)
#define bitcnt(x) (__builtin_popcountll(x))
#define complete_unique(a) a.erase(unique(begin(a), end(a)), end(a))
#define mst(x, a) memset(x, a, sizeof(x))
#define MP make_pair

using ll = long long;
using ull = unsigned long long;
using db = double;
using ld = long double;
using VLL = std::vector<ll>;
using VI = std::vector<int>;
using PII = std::pair<int, int>;
using PLL = std::pair<ll, ll>;

using namespace __gnu_pbds;
using namespace std;
template <typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

template <typename T, typename S>
inline bool chmax(T &a, const S &b) {
return a < b ? a = b, 1 : 0;
}

template <typename T, typename S>
inline bool chmin(T &a, const S &b) {
return a > b ? a = b, 1 : 0;
}

#ifdef LOCAL
#include <debug.hpp>
#else
#define dbg(...)
#endif

class Solution {
public:
long long appealSum(string s) {
ll res = 0;
auto pos = vector<int>(26, -1);

auto calc = [&](int r) -> ll {
ll res = 0;

auto f = vector<int>(pos);

sort(f.begin(), f.end());
reverse(f.begin(), f.end());

int cur = 0;

for (int i = 0; i < 26; i++) {
if (f[i] == -1) {
break;
}

res += 1ll * (r - f[i]) * cur;
r = f[i];

++cur;
}

res += 1ll * (r + 1) * cur;

return res;
};

int n = static_cast<int>(s.length());
for (int i = 0; i < n; i++) {
char c = s[i];
pos[c - 'a'] = i;

res += calc(i);

// cout << calc(i) << endl;
}

// cout << "---" << endl;

return res;
}
};

#ifdef LOCAL

int main() {
return 0;
}

#endif
``````