Huahua’s Tech Road

花花酱 LeetCode 1898. Maximum Number of Removable Characters

By zxi on August 11, 2021

You are given two strings s and p where p is a subsequence of s. You are also given a distinct 0-indexed integer array removable containing a subset of indices of s (s is also 0-indexed).

You want to choose an integer k (0 <= k <= removable.length) such that, after removing k characters from s using the first k indices in removable, p is still a subsequence of s. More formally, you will mark the character at s[removable[i]] for each 0 <= i < k, then remove all marked characters and check if p is still a subsequence.

Return the maximum k you can choose such that p is still a subsequence of s after the removals.

A subsequence of a string is a new string generated from the original string with some characters (can be none) deleted without changing the relative order of the remaining characters.

Example 1:

Input: s = "abcacb", p = "ab", removable = [3,1,0]
Output: 2
Explanation: After removing the characters at indices 3 and 1, "abcacb" becomes "accb".
"ab" is a subsequence of "accb".
If we remove the characters at indices 3, 1, and 0, "abcacb" becomes "ccb", and "ab" is no longer a subsequence.
Hence, the maximum k is 2.

Example 2:

Input: s = "abcbddddd", p = "abcd", removable = [3,2,1,4,5,6]
Output: 1
Explanation: After removing the character at index 3, "abcbddddd" becomes "abcddddd".
"abcd" is a subsequence of "abcddddd".

Example 3:

Input: s = "abcab", p = "abc", removable = [0,1,2,3,4]
Output: 0
Explanation: If you remove the first index in the array removable, "abc" is no longer a subsequence.

Constraints:

1 <= p.length <= s.length <= 10⁵
0 <= removable.length < s.length
0 <= removable[i] < s.length
p is a subsequence of s.
s and p both consist of lowercase English letters.
The elements in removable are distinct.

Solution: Binary Search + Two Pointers

If we don’t remove any thing, p is a subseq of s, as we keep removing, at some point L, p is no longer a subseq of s. e.g [0:True, 1: True, …, L – 1: True, L: False, L+1: False, …, m:False], this array is monotonic. We can use binary search to find the smallest L such that p is no long a subseq of s. Ans = L – 1.

For each guess, we can use two pointers to check whether p is subseq of removed(s) in O(n).

Time complexity: O(nlogn)
Space complexity: O(n)

C++

// Author: Huahua

class Solution {

public:

int maximumRemovals(string s, string p, vector<int>& removable) {

const int n = s.length();

const int t = p.length();

const int m = removable.size();

int l = 0;

int r = m + 1;

vector<int> idx(n, INT_MAX);

for (int i = 0; i < m; ++i)

idx[removable[i]] = i;

while (l < r) {

int mid = l + (r - l) / 2;

int j = 0;

for (int i = 0; i < n && j < t; ++i)

if (idx[i] >= mid && s[i] == p[j]) ++j;

if (j != t)

r = mid;

else

l = mid + 1;

}

// l is the smallest number s.t. p is no longer a subseq of s.

return l - 1;

}

};

花花酱 LeetCode 1897. Redistribute Characters to Make All Strings Equal

By zxi on August 11, 2021

You are given an array of strings words (0-indexed).

In one operation, pick two distinct indices i and j, where words[i] is a non-empty string, and move any character from words[i] to any position in words[j].

Return true if you can make every string in words equal using any number of operations, and false otherwise.

Example 1:

Input: words = ["abc","aabc","bc"]
Output: true
Explanation: Move the first 'a' in words[1] to the front of words[2],
to make words[1] = "abc" and words[2] = "abc".
All the strings are now equal to "abc", so return true.

Example 2:

Input: words = ["ab","a"]
Output: false
Explanation: It is impossible to make all the strings equal using the operation.

Constraints:

1 <= words.length <= 100
1 <= words[i].length <= 100
words[i] consists of lowercase English letters.

Solution: Hashtable

Count the frequency of each character, it must be a multiplier of n such that we can evenly distribute it to all the words.
e.g. n = 3, a = 9, b = 6, c = 3, each word will be “aaabbc”.

Time complexity: O(n)
Space complexity: O(1)

C++

// Author: Huahua

class Solution {

public:

bool makeEqual(vector<string>& words) {

vector<int> freq(26);

for (const auto& word : words)

for (char c : word)

++freq[c - 'a'];

for (int f : freq)

if (f % words.size()) return false;

return true;

}

};

Python3 one-liner

# Author: Huahua

class Solution:

def makeEqual(self, words: List[str]) -> bool:

return all(c % len(words) == 0 for c in Counter(''.join(words)).values())

花花酱 LeetCode 1896. Minimum Cost to Change the Final Value of Expression

By zxi on August 9, 2021

You are given a valid boolean expression as a string expression consisting of the characters '1','0','&' (bitwise AND operator),'|' (bitwise OR operator),'(', and ')'.

For example, "()1|1" and "(1)&()" are not valid while "1", "(((1))|(0))", and "1|(0&(1))" are valid expressions.

Return the minimum cost to change the final value of the expression.

For example, if expression = "1|1|(0&0)&1", its value is 1|1|(0&0)&1 = 1|1|0&1 = 1|0&1 = 1&1 = 1. We want to apply operations so that the new expression evaluates to 0.

The cost of changing the final value of an expression is the number of operations performed on the expression. The types of operations are described as follows:

Turn a '1' into a '0'.
Turn a '0' into a '1'.
Turn a '&' into a '|'.
Turn a '|' into a '&'.

Note: '&' does not take precedence over '|' in the order of calculation. Evaluate parentheses first, then in left-to-right order.

Example 1:

Input: expression = "1&(0|1)"
Output: 1
Explanation: We can turn "1&(0|1)" into "1&(0&1)" by changing the '|' to a '&' using 1 operation.
The new expression evaluates to 0.

Example 2:

Input: expression = "(0&0)&(0&0&0)"

Output: 3

Explanation: We can turn "(0&0)&(0&0&0)" into "(0|1)|(0&0&0)" using 3 operations.

The new expression evaluates to 1.

Example 3:

Input: expression = "(0|(1|0&1))"
Output: 1
Explanation: We can turn "(0|(1|0&1))" into "(0|(0|0&1))" using 1 operation.
The new expression evaluates to 0.

Constraints:

1 <= expression.length <= 10⁵
expression only contains '1','0','&','|','(', and ')'
All parentheses are properly matched.
There will be no empty parentheses (i.e: "()" is not a substring of expression).

Solution: DP, Recursion / Simulation w/ Stack

For each expression, stores the min cost to change value to 0 and 1.

Time complexity: O(n)
Space complexity: O(1)

C++

class Solution {

public:

int minOperationsToFlip(string expression) {

stack<array<int, 3>> s;

s.push({0, 0, 0});

for (char e : expression) {

if (e == '(')

s.push({0, 0, 0});

else if (e == '&' || e == '|')

s.top()[2] = e;

else {

if (isdigit(e)) s.push({e != '0', e != '1', 0});

auto [r0, r1, _] = s.top(); s.pop();

auto [l0, l1, op] = s.top(); s.pop();

if (op == '&') {

s.push({min(l0, r0),

min(l1 + r1, min(l1, r1) + 1),

0});

} else if (op == '|') {

s.push({min(l0 + r0, min(l0, r0) + 1),

min(l1, r1),

0});

} else {

s.push({r0, r1, 0});

}

return max(s.top()[0], s.top()[1]);

}

};

花花酱 LeetCode 1895. Largest Magic Square

By zxi on August 9, 2021

A k x k magic square is a k x k grid filled with integers such that every row sum, every column sum, and both diagonal sums are all equal. The integers in the magic square do not have to be distinct. Every 1 x 1 grid is trivially a magic square.

Given an m x n integer grid, return the size (i.e., the side length k) of the largest magic square that can be found within this grid.

Example 1:

Input: grid = [[7,1,4,5,6],[2,5,1,6,4],[1,5,4,3,2],[1,2,7,3,4]]
Output: 3
Explanation: The largest magic square has a size of 3.
Every row sum, column sum, and diagonal sum of this magic square is equal to 12.
- Row sums: 5+1+6 = 5+4+3 = 2+7+3 = 12
- Column sums: 5+5+2 = 1+4+7 = 6+3+3 = 12
- Diagonal sums: 5+4+3 = 6+4+2 = 12

Example 2:

Input: grid = [[5,1,3,1],[9,3,3,1],[1,3,3,8]]
Output: 2

Constraints:

m == grid.length
n == grid[i].length
1 <= m, n <= 50
1 <= grid[i][j] <= 10⁶

Solution: Brute Force w/ Prefix Sum

Compute the prefix sum for each row and each column.

And check all possible squares.

Time complexity: O(m*n*min(m,n)²)
Space complexity: O(m*n)

C++

// Author: Huahua

class Solution {

public:

int largestMagicSquare(vector<vector<int>>& grid) {

const int m = grid.size();

const int n = grid[0].size();

vector<vector<int>> rows(m, vector<int>(n + 1));

vector<vector<int>> cols(n, vector<int>(m + 1));

for (int i = 0; i < m; ++i)

for (int j = 0; j < n; ++j) {

rows[i][j + 1] = rows[i][j] + grid[i][j];

cols[j][i + 1] = cols[j][i] + grid[i][j];

}

for (int k = min(m, n); k >= 2; --k)

for (int i = 0; i + k <= m; ++i)

for (int j = 0; j + k <= n; ++j) {

vector<int> s;

for (int r = 0; r < k; ++r)

s.push_back(rows[i + r][j + k] - rows[i + r][j]);

for (int c = 0; c < k; ++c)

s.push_back(cols[j + c][i + k] - cols[j + c][i]);

int d1 = 0;

int d2 = 0;

for (int d = 0; d < k; ++d) {

d1 += grid[i + d][j + d];

d2 += grid[i + d][j + k - d - 1];

}

s.push_back(d1);

s.push_back(d2);

if (count(begin(s), end(s), s[0]) == s.size()) return k;

}

return 1;

}

};

花花酱 LeetCode 1894. Find the Student that Will Replace the Chalk

By zxi on August 9, 2021

There are n students in a class numbered from 0 to n - 1. The teacher will give each student a problem starting with the student number 0, then the student number 1, and so on until the teacher reaches the student number n - 1. After that, the teacher will restart the process, starting with the student number 0 again.

You are given a 0-indexed integer array chalk and an integer k. There are initially k pieces of chalk. When the student number i is given a problem to solve, they will use chalk[i] pieces of chalk to solve that problem. However, if the current number of chalk pieces is strictly less than chalk[i], then the student number i will be asked to replace the chalk.

Return the index of the student that will replace the chalk.

Example 1:

Input: chalk = [5,1,5], k = 22
Output: 0
Explanation: The students go in turns as follows:
- Student number 0 uses 5 chalk, so k = 17.
- Student number 1 uses 1 chalk, so k = 16.
- Student number 2 uses 5 chalk, so k = 11.
- Student number 0 uses 5 chalk, so k = 6.
- Student number 1 uses 1 chalk, so k = 5.
- Student number 2 uses 5 chalk, so k = 0.
Student number 0 does not have enough chalk, so they will have to replace it.

Example 2:

Input: chalk = [3,4,1,2], k = 25
Output: 1
Explanation: The students go in turns as follows:
- Student number 0 uses 3 chalk so k = 22.
- Student number 1 uses 4 chalk so k = 18.
- Student number 2 uses 1 chalk so k = 17.
- Student number 3 uses 2 chalk so k = 15.
- Student number 0 uses 3 chalk so k = 12.
- Student number 1 uses 4 chalk so k = 8.
- Student number 2 uses 1 chalk so k = 7.
- Student number 3 uses 2 chalk so k = 5.
- Student number 0 uses 3 chalk so k = 2.
Student number 1 does not have enough chalk, so they will have to replace it.

Constraints:

chalk.length == n
1 <= n <= 10⁵
1 <= chalk[i] <= 10⁵
1 <= k <= 10⁹

Solution: Math

Sum up all the students. k %= sum to skip all the middle rounds.

Time complexity: O(n)
Space complexity: O(1)

C++

// Author: Huahua

class Solution {

public:

int chalkReplacer(vector<int>& chalk, int k) {

long sum = accumulate(begin(chalk), end(chalk), 0L);

k %= sum;

for (size_t i = 0; i < chalk.size(); ++i)

if ((k -= chalk[i]) < 0) return i;

return -1;

}

};

Huahua's Tech Road

花花酱 LeetCode 1898. Maximum Number of Removable Characters

Solution: Binary Search + Two Pointers

C++

花花酱 LeetCode 1897. Redistribute Characters to Make All Strings Equal

Solution: Hashtable

C++

Python3 one-liner

花花酱 LeetCode 1896. Minimum Cost to Change the Final Value of Expression

Solution: DP, Recursion / Simulation w/ Stack

C++

花花酱 LeetCode 1895. Largest Magic Square

Solution: Brute Force w/ Prefix Sum

C++

花花酱 LeetCode 1894. Find the Student that Will Replace the Chalk

Solution: Math

C++