[Problem 1] Maximum Difference Between Even and Odd Frequency I
To get the correct answer, we should find the character that appears most at odd times and the one that appears least at even times.
So, I iterate the input string and record the frequency for all characters. Then, I calculate the maximum odd frequency and minimum even frequency. In this case, we cannot use characters that are not shown.
class Solution {
public:
int maxDifference(string s) {
vector<int> cnt(26, 0);
for (auto &c:s)cnt[c-'a']++;
int maxOdd = 0, minEven = 1e9;
for (auto & x:cnt) {
if (x == 0) continue;
if (x % 2 == 0) minEven = min(minEven, x);
else maxOdd = max(maxOdd, x);
}
return maxOdd - minEven;
}
};
[Problem 2] Maximum Manhattan Distance After K Changes
In this problem, we should find the maximum Manhattan distance from (0, 0). We can calculate the Manhattan distance by [X1 - X0| + [Y1 - Y0|. If we want it to be maximum, we should minimize the opposite moves, such as N-S and W-E.
So, we can simply choose a maximum of one from N/S and one from W/E. Then, we can change the direction at most K from both minimum directions.
For example, N = 6, S = 4, E = 5, W = 2, K = 5
Then, we can choose N and E.
We change 4 S to 4 N and 1 W to 1 E (Total K times).
Then it became N= 10, S = 0, E = 6, W = 1, so the answer is 15.
We should check the answer at each index. The maximum can be found in the middle of the moves.
class Solution {
public:
int maxDistance(string S, int k) {
int n = 0, w = 0, s = 0, e = 0, ans = 0;
for (auto & c:S) {
if (c == 'N') n++;
else if (c == 'W') w++;
else if (c == 'S') s++;
else e++;
int curr = max(n, s) + max(w, e), minus = min(n, s) + min(w, e);
int changed = min(minus, k);
minus -= changed;
curr += changed;
curr -= minus;
ans = max(ans, curr);
}
return ans;
}
};
[Problem 3] Minimum Increments for Target Multiples in an Array
In this problem, we should find the minimum increments to meet the condition. The critical point is that we only can increase the element. By this restriction, we can calculate the minimum value to make nums[i] to be the multiple of targets[j].
However, we don’t know which number will be the multiple of which target. Also, one number can be the multiple of two different targets. We cannot consider all of these cases one by one.
Fortunately, we only have at most 4 targets. It means that if we calculate all the cases that nums[i] cover, it is at most 2^4 = 16. So, it is fast enough to iterate all cases for each index i of nums.
I precalculated the Least Common Multiple for each target combination to get the minimum increment faster. I record the state to find which targets are covered. If all targets are covered before iterating all nums, then return 0. If iterating all numbers finished before covering all targets, return an invalid value.
I also used memoization to skip the duplicated case.
class Solution {
public:
int n, m;
unordered_map<int, long long> mp;
int dp[50001][1<<4];
long long func(vector<int> & nums, vector<int> & target, int i, int state) {
if (state == (1<<m) - 1) {
return 0;
}
if (i == n) {
return 1e9;
}
if (dp[i][state] != -1) return dp[i][state];
long long ans = 1e9;
for (int x = 0; x < (1 << m); ++x) {
long long l = mp[x];
long long diff = ((nums[i] + l-1) / l) * l - nums[i];
ans = min(ans, func(nums, target, i+1, state | x) + diff);
}
return dp[i][state] = ans;
}
int minimumIncrements(vector<int>& nums, vector<int>& target) {
n = (int)nums.size();
m = (int)target.size();
memset(dp, -1,sizeof(dp));
mp[0] = 1;
for (int x = 1; x < (1 << m); ++x) {
vector<long long> a;
for (int j = 0; j < m; ++j) {
if (x & (1 << j)) {
a.push_back(target[j]);
}
}
long long l = a[0];
for (int i = 1; i < a.size(); ++i) {
l = l * a[i] / gcd(l, a[i]);
}
mp[x] = l;
}
return func(nums, target, 0, 0);
}
};
[Problem 4] Maximum Difference Between Even and Odd Frequency II
We should find the maximum difference between odd frequency and even frequency. This problem is the hard version of problem 1. The reason why the first problem is easy is that the size of the string is fixed. We only need to care about the frequency of each character.
However, we can't use the same strategy in this problem because we don’t know the size. If we fix the size, we should iterate every character of the input string for each possible size larger than K. If K == 1, then it should take O((26) * N^2) times. So, this won’t work.
Fortunately, we know that there are only 5 characters that can be shown in the input string. We don’t know which one will be the answer, but the answer case will use only 2 characters: One for the odd frequency and one for the even frequency. Also, there are only 20 possible combinations. Assuming the characters for counting and getting the answer within O(N) or O(NlogN) time complexity, iterating 20 times wouldn’t be the problem.
So, I tried to consider the case when only two characters exist. Let’s ignore the size of substring K.
How to calculate the frequency for a range query.
To get the correct answer, we should find the exact case where an odd frequency character should appear at odd times and an even frequency character should appear at even times. But we are not sure if index i
will meet the conditions. We should remove the character from the start if it does not meet. In short, we should calculate the count for each character within the range of [left, right].
To calculate it faster, I precalculate the prefix sum, which contains the frequency data of the odd-frequency character and the even-frequency character within [0, i]. To find out the counting status of [i, j], we can simply subtract the prefixSum[i-1] from the prefixSum[j].
How can we ensure the proper case for the answer?
Now, we should find the right index i where [i, j] is the possible case for the answer. It means that when we iterate the input string, we should find the left index that will meet the condition. This is pretty complex.
What I thought of was the following conditions:
We have already set the odd-frequency character and even-frequency character, and my goal is to find the case where an odd-frequency character appears at odd times, and the even-frequency character appears at even times.
If both characters appear at even times at index i, I should find the left index where an odd-frequency character appears at odd times and the even-frequency character appears at even times.
For example, both characters appear 6 times at index i. If we found the j where j < i and odd-frequency character appeared 3 times and even-frequency character appeared 2 times.
If we remove the characters [0,j] from [0, i], then [j+1, i] will meet the condition because odd-frequency appeared 3 times(6 - 3), and even-frequency appeared 4 times(6 -2).
In short, we can record each counting status at each index i and then find the correct index for the right counting status type.
There will be four different statuses.
(Odd, Even) = odd-frequency appears odd times, even-frequency appears even times,
(Even, Even) = odd-frequency appears even times, even-frequency appears even times,
(Odd, Odd) = odd-frequency appears odd times, even-frequency appears odd times,
(Even, Odd) = odd-frequency appears even times, even-frequency appears odd times,
To get the (Odd, Even) case, we can find the correct status for removal.
(Odd, Even) - (Even, Even) = (Odd, Even)
(Even, Even) - (Odd, Even) = (Odd, Even)
(Odd, Odd) - (Even, Odd) = (Odd, Even)
(Even, Odd) - (Odd, Odd) = (Odd, Even)
This can be implemented by recording the types at each index i and enqueuing them to each type queue. We can then find the index j for removal from the matching status type queue at index i.
If (Odd, Even) is at index i, find the index from the (Even, Even) queue.
How can we ensure the size of the substring?
To ensure the size of the substring, we can use a pointer to follow the index to keep the size of the substring and enqueue the value for each type of queue. We cannot calculate the answer before we enqueue the value to the queue. This means we should ensure that the enqueued items are okay to get the answer.
So, if the i—(left index) >= K meets, we can enqueue the left index item to the queue and then move the left index to the right.
class Solution {
public:
int func(string & s, int k, char & oddChar, char & evenChar) {
const int n = (int)s.size();
vector<vector<int>> cnt(n, vector<int>(2));
int oddCharCnt = 0, evenCharCnt = 0;
vector<int> T(n);
for (int i = 0; i < n; ++i) {
if (s[i] == oddChar) oddCharCnt++;
else if (s[i] == evenChar) evenCharCnt++;
cnt[i][0] = oddCharCnt, cnt[i][1] = evenCharCnt;
if (oddCharCnt % 2 == 0 && evenCharCnt % 2 == 1) T[i] = 0;
else if (oddCharCnt % 2 == 0 && evenCharCnt % 2 == 0) T[i] = 1;
else if (oddCharCnt % 2 == 1 && evenCharCnt % 2 == 0) T[i] = 2;
else T[i] = 3;
}
int ans = -1e9, curr = 0, l = 0;
auto getOppositeIndex = [&] (int t) {
if (t == 0) return 3;
if (t == 1) return 2;
if (t == 2) return 1;
return 0;
};
auto isPossible = [&] (int i, int j) {
int oddCharCnt = cnt[i][0] - (j == -1 ? 0 : cnt[j][0]);
int evenCharCnt = cnt[i][1] - (j == -1 ? 0 : cnt[j][1]);
return oddCharCnt > 0 && evenCharCnt > 0 && oddCharCnt % 2 == 1 && evenCharCnt % 2 == 0 && i - j >= k;
};
vector<int> minimumCanRemove(4, 1e9);
queue<int> q[4];
for (int i = 0; i < n; ++i) {
int curr = cnt[i][0] - cnt[i][1];
while(i - l >= k) {
q[T[l]].push(l);
++l;
}
int oppositeType = getOppositeIndex(T[i]);
while(!q[oppositeType].empty() && isPossible(i, q[oppositeType].front())) {
int prevIdx = q[oppositeType].front();
q[oppositeType].pop();
minimumCanRemove[oppositeType] = min(minimumCanRemove[oppositeType], cnt[prevIdx][0] - cnt[prevIdx][1]);
}
ans = max(ans, curr - minimumCanRemove[oppositeType]);
if (T[i] == 2 && isPossible(i, -1)) ans = max(ans, curr);
}
return ans;
}
int maxDifference(string s, int k) {
int ans = INT_MIN;
for (char i = '0'; i <= '4'; ++i) {
for (char j = '0'; j <= '4'; ++j) {
if (i == j) continue;
ans = max(ans, func(s, k, i, j));
}
}
return ans;
}
};