Huahua's Tech Road

花花酱 LeetCode 1191. K-Concatenation Maximum Sum

By zxi on September 15, 2019

Given an integer array arr and an integer k, modify the array by repeating it k times.

For example, if arr = [1, 2] and k = 3 then the modified array will be [1, 2, 1, 2, 1, 2].

Return the maximum sub-array sum in the modified array. Note that the length of the sub-array can be 0 and its sum in that case is 0.

As the answer can be very large, return the answer modulo 10^9 + 7.

Example 1:

Input: arr = [1,2], k = 3
Output: 9

Example 2:

Input: arr = [1,-2,1], k = 5
Output: 2

Example 3:

Input: arr = [-1,-2], k = 7
Output: 0

Constraints:

1 <= arr.length <= 10^5
1 <= k <= 10^5
-10^4 <= arr[i] <= 10^4

Solution: DP

This problem can be reduced to maxSubarray.
If k < 3: return maxSubarray(arr * k)
ans1 = maxSubarray(arr * 1)
ans2 = maxSubarray(arr * 2)
ans = max([ans1, ans2, ans2 + sum(arr) * (k – 2)])

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

C++

// Author: Huahua

class Solution {

public:

int kConcatenationMaxSum(vector<int>& arr, int k) {

constexpr int kMod = 1e9 + 7;

auto maxSum = [&arr](int r) {

long sum = 0;

long ans = 0;

for (int i = 0; i < r; ++i) {

for (long a : arr) {

sum = max(0L, sum += a);

ans = max(ans, sum);

}

return ans;

};

if (k < 3) return maxSum(k) % kMod;

long ans1 = maxSum(1);

long ans2 = maxSum(2);

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

return max({ans1, ans2, ans2 + sum * (k - 2)}) % kMod;

}

};

花花酱 LeetCode 1190. Reverse Substrings Between Each Pair of Parentheses

By zxi on September 15, 2019

Given a string s that consists of lower case English letters and brackets.

Reverse the strings in each pair of matching parentheses, starting from the innermost one.

Your result should not contain any bracket.

Example 1:

Input: s = "(abcd)"
Output: "dcba"

Example 2:

Input: s = "(u(love)i)"
Output: "iloveu"

Example 3:

Input: s = "(ed(et(oc))el)"
Output: "leetcode"

Example 4:

Input: s = "a(bcdefghijkl(mno)p)q"
Output: "apmnolkjihgfedcbq"

Constraints:

0 <= s.length <= 2000
s only contains lower case English characters and parentheses.
It’s guaranteed that all parentheses are balanced.

Solution: Stack

Use a stack of strings to track all the active strings.
Iterate over the input string:
1. Whenever there is a ‘(‘, push an empty string to the stack.
2. Whenever this is a ‘)’, pop the top string and append the reverse of it to the new stack top.
3. Otherwise, append the letter to the string on top the of stack.

Once done, the (only) string on the top of the stack is the answer.

Time complexity: O(n^2)
Space complexity: O(n)

C++

// Author: Huahua

class Solution {

public:

string reverseParentheses(string s) {

stack<string> st;

st.push("");

for (char c : s) {

if (c == '(') st.push("");

else if (c != ')') st.top() += c;

else {

string t = st.top(); st.pop();

st.top().insert(end(st.top()), rbegin(t), rend(t));

}

return st.top();

}

};

花花酱 LeetCode 1189. Maximum Number of Balloons

By zxi on September 15, 2019

Given a string text, you want to use the characters of text to form as many instances of the word “balloon” as possible.

You can use each character in text at most once. Return the maximum number of instances that can be formed.

Example 1:

Input: text = "nlaebolko"
Output: 1

Example 2:

Input: text = "loonbalxballpoon"
Output: 2

Example 3:

Input: text = "leetcode"
Output: 0

Constraints:

1 <= text.length <= 10^4
text consists of lower case English letters only.

Solution: HashTable

Use a hashtable to count the occurrence of each letter and find the bottleneck one.

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

C++

// Author: Huahua

class Solution {

public:

int maxNumberOfBalloons(string text) {

map<char, int> c;

for (char t : text) ++c[t];

return min({c['b'], c['a'], c['l'] / 2, c['o'] / 2, c['n']});

}

};

花花酱 LeetCode 1187. Make Array Strictly Increasing

By zxi on September 7, 2019

Given two integer arrays arr1 and arr2, return the minimum number of operations (possibly zero) needed to make arr1 strictly increasing.

In one operation, you can choose two indices 0 <= i < arr1.length and 0 <= j < arr2.length and do the assignment arr1[i] = arr2[j].

If there is no way to make arr1 strictly increasing, return -1.

Example 1:

Input: arr1 = [1,5,3,6,7], arr2 = [1,3,2,4]
Output: 1
Explanation: Replace 5 with 2, then arr1 = [1, 2, 3, 6, 7].

Example 2:

Input: arr1 = [1,5,3,6,7], arr2 = [4,3,1]
Output: 2
Explanation: Replace 5 with 3 and then replace 3 with 4. arr1 = [1, 3, 4, 6, 7].

Example 3:

Input: arr1 = [1,5,3,6,7], arr2 = [1,6,3,3]
Output: -1
Explanation: You can't make arr1 strictly increasing.

Constraints:

1 <= arr1.length, arr2.length <= 2000
0 <= arr1[i], arr2[i] <= 10^9

Solution: DP

Time complexity: O(mn)
Space complexity: O(mn) -> O(m + n)

C++

// Author: Huahua

class Solution {

public:

int makeArrayIncreasing(vector<int>& a, vector<int>& c) {

constexpr int kInf = 1e9;

int m = a.size();

// Sort b and make it only containing unique numbers.

sort(begin(c), end(c));

vector<int> b;

for (int i = 0; i < c.size(); ++i) {

if (!b.empty() && c[i] == b.back()) continue;

b.push_back(c[i]);

}

int n = b.size();

// min steps to make a[0~i] valid by keeping a[i]

vector<int> keep(m, kInf);

keep[0] = 0;

// swap[i][j] := min steps to make a[0~i] valid by a[i] = b[j]

vector<int> swap(n, 1);

for (int i = 1; i < m; ++i) {

int min_keep = kInf;

int min_swap = kInf;

vector<int> temp(n, kInf);

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

if (j > 0) min_swap = min(min_swap, swap[j - 1] + 1);

if (a[i] > b[j]) min_keep = min(min_keep, swap[j]);

if (a[i] > a[i - 1]) keep[i] = keep[i - 1];

if (b[j] > a[i - 1]) temp[j] = keep[i - 1] + 1;

temp[j] = min(temp[j], min_swap);

keep[i] = min(keep[i], min_keep);

}

temp.swap(swap);

}

int s = *min_element(begin(swap), end(swap));

int k = keep.back();

int ans = min(s, k);

return ans >= kInf ? -1 : ans;

}

};

花花酱 LeetCode 1186. Maximum Subarray Sum with One Deletion

By zxi on September 7, 2019

Given an array of integers, return the maximum sum for a non-empty subarray (contiguous elements) with at most one element deletion. In other words, you want to choose a subarray and optionally delete one element from it so that there is still at least one element left and the sum of the remaining elements is maximum possible.

Note that the subarray needs to be non-empty after deleting one element.

Example 1:

Input: arr = [1,-2,0,3]
Output: 4
Explanation: Because we can choose [1, -2, 0, 3] and drop -2, thus the subarray [1, 0, 3] becomes the maximum value.

Example 2:

Input: arr = [1,-2,-2,3]
Output: 3
Explanation: We just choose [3] and it's the maximum sum.

Example 3:

Input: arr = [-1,-1,-1,-1]
Output: -1
Explanation: The final subarray needs to be non-empty. You can't choose [-1] and delete -1 from it, then get an empty subarray to make the sum equals to 0.

Constraints:

1 <= arr.length <= 10^5
-10^4 <= arr[i] <= 10^4

Solution: DP

First, handle the special case: all numbers are negative, return the max one.

s0 = max subarray sum ends with a[i]
s1 = max subarray sum ends with a[i] with at most one deletion

whenever s0 or s1 becomes negative, reset them to 0.

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

C++

// Author: Huahua

class Solution {

public:

int maximumSum(vector<int>& arr) {

int m = *max_element(begin(arr), end(arr));

if (m <= 0) return m;

int s0 = 0;

int s1 = 0;

int ans = 0;

for (int a : arr) {

s1 = max(s0, s1 + a);

s0 += a;

ans = max(ans, max(s0, s1));

if (s0 < 0) s0 = 0;

if (s1 < 0) s1 = 0;

}

return ans;

}

};