Huahua’s Tech Road

花花酱 LeetCode 1750. Minimum Length of String After Deleting Similar Ends

By zxi on February 6, 2021

Given a string s consisting only of characters 'a', 'b', and 'c'. You are asked to apply the following algorithm on the string any number of times:

Pick a non-empty prefix from the string s where all the characters in the prefix are equal.
Pick a non-empty suffix from the string s where all the characters in this suffix are equal.
The prefix and the suffix should not intersect at any index.
The characters from the prefix and suffix must be the same.
Delete both the prefix and the suffix.

Return the minimum length of s after performing the above operation any number of times (possibly zero times).

Example 1:

Input: s = "ca"
Output: 2
Explanation: You can't remove any characters, so the string stays as is.

Example 2:

Input: s = "cabaabac"
Output: 0
Explanation: An optimal sequence of operations is:
- Take prefix = "c" and suffix = "c" and remove them, s = "abaaba".
- Take prefix = "a" and suffix = "a" and remove them, s = "baab".
- Take prefix = "b" and suffix = "b" and remove them, s = "aa".
- Take prefix = "a" and suffix = "a" and remove them, s = "".

Example 3:

Input: s = "aabccabba"
Output: 3
Explanation: An optimal sequence of operations is:
- Take prefix = "aa" and suffix = "a" and remove them, s = "bccabb".
- Take prefix = "b" and suffix = "bb" and remove them, s = "cca".

Constraints:

1 <= s.length <= 10⁵
s only consists of characters 'a', 'b', and 'c'.

Solution: Two Pointers + Greedy

Delete all the chars for each prefix and suffix pair.

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

C++

// Author: Huahua

class Solution {

public:

int minimumLength(string s) {

int l = 0, r = s.length() - 1;

while (l < r) {

if (s[l] != s[r]) break;

const char c = s[l];

while (l <= r && s[l] == c) ++l;

while (l <= r && s[r] == c) --r;

}

return r - l + 1;

}

};

花花酱 LeetCode 1749. Maximum Absolute Sum of Any Subarray

By zxi on February 6, 2021

You are given an integer array nums. The absolute sum of a subarray [nums_l, nums_l+1, ..., nums_r-1, nums_r] is abs(nums_l + nums_l+1 + ... + nums_r-1 + nums_r).

Return the maximum absolute sum of any (possibly empty) subarray of nums.

Note that abs(x) is defined as follows:

If x is a negative integer, then abs(x) = -x.
If x is a non-negative integer, then abs(x) = x.

Example 1:

Input: nums = [1,-3,2,3,-4]
Output: 5
Explanation: The subarray [2,3] has absolute sum = abs(2+3) = abs(5) = 5.

Example 2:

Input: nums = [2,-5,1,-4,3,-2]
Output: 8
Explanation: The subarray [-5,1,-4] has absolute sum = abs(-5+1-4) = abs(-8) = 8.

Constraints:

1 <= nums.length <= 10⁵
-10⁴ <= nums[i] <= 10⁴

Solution: Prefix Sum

ans = max{abs(prefix_sum[i] – max(prefix_sum[0:i])), abs(prefix_sum – min(prefix_sum[0:i])}

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

C++

// Author: Huahua

class Solution {

public:

int maxAbsoluteSum(vector<int>& nums) {

int lo = 0;

int hi = 0;

int s = 0;

int ans = 0;

for (int x : nums) {

s += x;

ans = max({ans, abs(s - lo), abs(s - hi)});

hi = max(hi, s);

lo = min(lo, s);

}

return ans;

}

};

花花酱 LeetCode 1748. Sum of Unique Elements

By zxi on February 6, 2021

You are given an integer array nums. The unique elements of an array are the elements that appear exactly once in the array.

Return the sum of all the unique elements of nums.

Example 1:

Input: nums = [1,2,3,2]
Output: 4
Explanation: The unique elements are [1,3], and the sum is 4.

Example 2:

Input: nums = [1,1,1,1,1]
Output: 0
Explanation: There are no unique elements, and the sum is 0.

Example 3:

Input: nums = [1,2,3,4,5]
Output: 15
Explanation: The unique elements are [1,2,3,4,5], and the sum is 15.

Constraints:

1 <= nums.length <= 100
1 <= nums[i] <= 100

Solution: Hashtable

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

C++

// Author: Huahua

class Solution {

public:

int sumOfUnique(vector<int>& nums) {

vector<int> seen(101);

int ans = 0;

for (int x : nums)

++seen[x];

for (int x : nums)

if (seen[x] == 1) ans += x;

return ans;

}

};

花花酱 LeetCode 1745. Palindrome Partitioning IV

By zxi on January 30, 2021

Given a string s, return true if it is possible to split the string s into three non-empty palindromic substrings. Otherwise, return false.

A string is said to be palindrome if it the same string when reversed.

Example 1:

Input: s = "abcbdd"
Output: true
Explanation: "abcbdd" = "a" + "bcb" + "dd", and all three substrings are palindromes.

Example 2:

Input: s = "bcbddxy"
Output: false
Explanation: s cannot be split into 3 palindromes.

Constraints:

3 <= s.length <= 2000
s consists only of lowercase English letters.

Solution: DP

dp[i][j] := whether s[i]~s[j] is a palindrome.

dp[i][j] = s[i] == s[j] and dp[i+1][j-1]

ans = any(dp[0][i-1] and dp[i][j] and dp[j][n-1]) for j in range(i, n – 1) for i in range(1, n)

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

C++

// Author: Huahua

class Solution {

public:

bool checkPartitioning(string s) {

const int n = s.length();

vector<vector<int>> dp(n, vector<int>(n, 1));

for (int l = 2; l <= n; ++l)

for (int i = 0, j = i + l - 1; j < n; ++i, ++j)

dp[i][j] = (s[i] == s[j]) && dp[i + 1][j - 1];

for (int i = 1; i < n; ++i)

for (int j = i; j + 1 < n; ++j)

if (dp[0][i - 1] && dp[i][j] && dp[j + 1][n - 1])

return true;

return false;

}

};

花花酱 LeetCode 1744. Can You Eat Your Favorite Candy on Your Favorite Day?

By zxi on January 30, 2021

You are given a (0-indexed) array of positive integers candiesCount where candiesCount[i] represents the number of candies of the i^th type you have. You are also given a 2D array queries where queries[i] = [favoriteType_i, favoriteDay_i, dailyCap_i].

You play a game with the following rules:

You start eating candies on day 0.
You cannot eat any candy of type i unless you have eaten all candies of type i - 1.
You must eat at least one candy per day until you have eaten all the candies.

Construct a boolean array answer such that answer.length == queries.length and answer[i] is true if you can eat a candy of type favoriteType_i on day favoriteDay_i without eating more than dailyCap_i candies on any day, and false otherwise. Note that you can eat different types of candy on the same day, provided that you follow rule 2.

Return the constructed array answer.

Example 1:

Input: candiesCount = [7,4,5,3,8], queries = [[0,2,2],[4,2,4],[2,13,1000000000]]
Output: [true,false,true]
Explanation:
1- If you eat 2 candies (type 0) on day 0 and 2 candies (type 0) on day 1, you will eat a candy of type 0 on day 2.
2- You can eat at most 4 candies each day.
   If you eat 4 candies every day, you will eat 4 candies (type 0) on day 0 and 4 candies (type 0 and type 1) on day 1.
   On day 2, you can only eat 4 candies (type 1 and type 2), so you cannot eat a candy of type 4 on day 2.
3- If you eat 1 candy each day, you will eat a candy of type 2 on day 13.

Example 2:

Input: candiesCount = [5,2,6,4,1], queries = [[3,1,2],[4,10,3],[3,10,100],[4,100,30],[1,3,1]]
Output: [false,true,true,false,false]

Constraints:

1 <= candiesCount.length <= 10⁵
1 <= candiesCount[i] <= 10⁵
1 <= queries.length <= 10⁵
queries[i].length == 3
0 <= favoriteType_i < candiesCount.length
0 <= favoriteDay_i <= 10⁹
1 <= dailyCap_i <= 10⁹

Solution: Prefix Sum

We must have enough capacity to eat all candies before the current type.
We must have at least prefix sum candies than days, since we have to eat at least one each day.

sum[i] = sum(candyCount[0~i])
ans = {days * cap > sum[type – 1] && days <= sum[type])

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

C++

// Author: Huhua

class Solution {

public:

vector<bool> canEat(vector<int>& candiesCount, vector<vector<int>>& queries) {

const int n = candiesCount.size();

vector<long> sums(n + 1);

for (int i = 1; i <= n; ++i)

sums[i] += sums[i - 1] + candiesCount[i - 1];

vector<bool> ans;

for (const auto& q : queries) {

const long type = q[0], days = q[1] + 1, cap = q[2];

ans.push_back(days * cap > sums[type] && days <= sums[type + 1]);

}

return ans;

}

};

Huahua's Tech Road

花花酱 LeetCode 1750. Minimum Length of String After Deleting Similar Ends

Solution: Two Pointers + Greedy

C++

花花酱 LeetCode 1749. Maximum Absolute Sum of Any Subarray

Solution: Prefix Sum

C++

花花酱 LeetCode 1748. Sum of Unique Elements

Solution: Hashtable

C++

花花酱 LeetCode 1745. Palindrome Partitioning IV

Solution: DP

C++

花花酱 LeetCode 1744. Can You Eat Your Favorite Candy on Your Favorite Day?

Solution: Prefix Sum

C++