Leetcode Weekly Contest 437
Leetcode Weekly Contest 437 with solution
Problem 1: Find a Special Substring of Length K
In this problem, we should find the substring with a fixed length that meets the following conditions.
The substring should use only 1 character.
The character placed right before and after the substring must not be the same as the character in the substring. It means that if there is a substring whose range is [l,r], then s[l-1] and s[r+1] must not be the character of s[l].
This is very easy because the length of the input string is really short. You can generate all possible substrings of length K and check if it is made with only 1 character. I used sorting to check this. After that, check if the same character exists before and after the substring.
class Solution {
public:
bool hasSpecialSubstring(string s, int k) {
for (int i = 0; i < s.size()-k+1; ++i) {
string sub = s.substr(i, k);
sort(sub.begin(), sub.end());
if (sub[0] == sub.back() && (i-1 < 0 || s[i-1] != sub[0]) && (i + k >= s.size() || s[i+k] != sub[0])) return true;
}
return false;
}
};Problem 2: Eat Pizzas!
We should find the maximum weight we can get after eating all the pizzas. No matter how we eat the pizza daily, we only get the maximum or the second maximum based on the day's index.
This problem is easy if you find the greedy solution where you can greedily choose the maximum on the odd day and the second largest on the even days. However you should ensure that this algorithm really works in this problem.
Here’s why the greedy algorithm works.
Let’s say there are piazzas like [1,2,3,4,5,6,7,8,9,10,11,12] (sorted order).
On the first day, we can choose a maximum of 12. (We should eat the three lightest pizzas together.) Then we only have [4,5,6,7,8,9,10,11]
On the second day, we choose the second largest one, 10. Then, we should choose 11 to make 10 the second largest. So, we only have [6,7,8,9].
On the third day, we gained 9 because it was the maximum weight.
However, if we choose [4,5,9,10] to achieve weight 9, we can achieve 11 on the third day.
It means that If there are three values [X, Y, Z] where X <= Y <= Z, then we can choose (X, Y) or (X, Z).
If we choose Y on the even-numbered day, then it will be (X, Y)
Otherwise, (X, Z).
X + Z is always larger than X + Y. Therefore, to get the maximum number, we should choose the odd-numbered day first.
So, we can choose the largest (total days + 1 / 2) weights first for the odd-numbered day, and then the second largest one for (total days / 2) times.
class Solution {
public:
long long maxWeight(vector<int>& pizzas) {
const int n = (int)pizzas.size();
sort(pizzas.rbegin(), pizzas.rend());
int days = n / 4;
int idx = 0;
long long sum = 0LL;
for (int i = 0; i < (days+1) / 2; ++i) {
sum += pizzas[idx++];
}
for (int i = 0; i < days / 2; ++i) {
sum += pizzas[++idx];
++idx;
}
return sum;
}
};Problem 3: Select K Disjoint Special Substrings
In this problem, one character should be in only one substring. If we choose the substring from the index [l, r], every character between them should not exist outside the range.
Fortunately, we have a maximum of 26 characters, so we can check all substrings that start with every character.
Get the start and end position of every character.
Sort the intervals based on the start.
Iterate the character from the one that appears at the latest. This is for the number of possible disjoint substrings after the current index.
For example, if the last index of the substring starting with index i is j, then we can get (dp[j+1] + 1) substrings. To get dp[j+1], we should calculate it before visiting the current index. So, we should iterate from the last.
Every character has its start and end index. However, the end index should be changed if another character has a more extensive index than the end index. Also, if there is a character that should start before the current start index, then we can skip the current character because it will be checked later.
For example, if the substring is “BABEAE” and the current character is A, the start index is 1, and the end index is 4.
However, E is between [1,4] and appears again after the end index of A. So, we should extend the end index to 5.
In this case, the character B exists between [1,4] and B should start before index 1. So, we have to skip to get the answer with a substring that begins with A because it is impossible.
This algorithm takes only O(26 * N) times because, for every character, we only iterate the input string at once.
class Solution {
public:
bool maxSubstringLength(string s, int k) {
vector<pair<int,int>> intervals(26, {-1, -1});
const int n = (int)s.size();
for (int i = 0; i < n; ++i) {
int j = s[i]-'a';
intervals[j].second = i;
if (intervals[j].first == -1) intervals[j].first = i;
}
vector<pair<int,int>> arr;
for (int i = 0; i < intervals.size(); ++i) {
if (intervals[i].first != -1) arr.push_back(intervals[i]);
}
sort(arr.begin(), arr.end());
vector<int> dp(arr.size()+1, 0);
int ans = 0;
for (int i = arr.size()-1; i >= 0; --i) {
dp[i] = max(dp[i], dp[i+1]);
int l = arr[i].first, r = arr[i].second;
int end = r;
bool flag = true;
for (int j = l+1; j < r; ++j) {
int ns = intervals[s[j]-'a'].first, ne = intervals[s[j]-'a'].second;
if (ns < l) {
flag = false;
break;
}
r = max(r, ne);
}
if (flag && r - l + 1 < s.size()) {
int idx = lower_bound(arr.begin(), arr.end(), make_pair(r, r)) - arr.begin();
dp[i] = max(dp[i], dp[idx] + 1);
}
ans = max(ans, dp[i]);
}
return ans >= k;
}
};Problem 4: Length of Longest V-Shaped Diagonal Segment
In this problem, we should find the most extended length that can be made with a 1,2,0,2,0 sequence. Unlike the typical DFS problem, we should move in a diagonal direction. Also, we can change the direction to one way and at most once.
The solution is basically the same as for the typical DFS problem. However, before proceeding, we should consider the following two cases.
Choose the same direction.
Choose to take a 90-degree clockwise turn. In this case, we should not change the direction before.
The value difference between the current and the following positions should be 2 for both cases.
So, for every position (x, y), we can keep track of the direction and the changed times. With this information, we can make all the possible moves.
However, if the grid size increases, we might visit the same position with the same condition more than once. So, we can use memoization to save the previous result and then return if we visit again. This can be possible because we have at most 500 * 500 * 4 * 2 cases. (500 - m, 500 - n, 4 - direction, 2 - the number of turns)
We don’t need to keep track of the previous visit during DFS because we cannot go back because we cannot change the direction 180 degrees. We cannot change the direction twice, so revisiting the same node within the single DFS traverse is impossible.
class Solution {
public:
int dx[4] = {1,1,-1,-1};
int dy[4] = {1,-1,-1,1};
int dp[501][501][4][2];
bool pos(int x, int y, int nx, int ny, vector<vector<int>> & grid) {
return nx >= 0 && ny >= 0 && nx < grid.size() && ny < grid[0].size() && abs(grid[x][y] - grid[nx][ny]) == 2;
}
int dfs(vector<vector<int>> & grid, int x, int y, int d, int changed) {
if (dp[x][y][d][changed] != -1) return dp[x][y][d][changed];
// follow the direction
int ans = 1;
if (pos(x, y, x + dx[d], y + dy[d], grid)) {
ans = max(ans, dfs(grid, x + dx[d], y + dy[d], d, changed) + 1);
}
// change the direction
if (changed == 0) {
int nd = (d + 1) % 4;
if (pos(x, y, x + dx[nd], y + dy[nd], grid)) {
ans = max(ans, dfs(grid, x + dx[nd], y + dy[nd], nd, changed+1) + 1);
}
}
return dp[x][y][d][changed] = ans;
}
int lenOfVDiagonal(vector<vector<int>>& grid) {
const int n = (int)grid.size();
const int m = (int)grid[0].size();
int ans = 0;
memset(dp, -1, sizeof(dp));
for (int i = 0; i < n; ++i) {
for (int j = 0; j < m; ++j) {
if (grid[i][j] == 1) {
ans = max(ans, 1);
for (int k = 0; k < 4; ++k) {
int nx = i + dx[k], ny = j + dy[k];
if (nx < 0 || ny < 0 || nx >= n || ny >= m || grid[nx][ny] != 2) continue;
ans = max(ans, dfs(grid, nx, ny, k, 0) + 1);
}
}
}
}
return ans;
}
};