Posts tagged as “medium”

花花酱 LeetCode 1930. Unique Length-3 Palindromic Subsequences

By zxi on December 30, 2021

Given a string s, return the number of unique palindromes of length three that are a subsequence of s.

Note that even if there are multiple ways to obtain the same subsequence, it is still only counted once.

A palindrome is a string that reads the same forwards and backwards.

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.

For example, "ace" is a subsequence of "abcde".

Example 1:

Input: s = "aabca"
Output: 3
Explanation: The 3 palindromic subsequences of length 3 are:
- "aba" (subsequence of "aabca")
- "aaa" (subsequence of "aabca")
- "aca" (subsequence of "aabca")

Example 2:

Input: s = "adc"
Output: 0
Explanation: There are no palindromic subsequences of length 3 in "adc".

Example 3:

Input: s = "bbcbaba"
Output: 4
Explanation: The 4 palindromic subsequences of length 3 are:
- "bbb" (subsequence of "bbcbaba")
- "bcb" (subsequence of "bbcbaba")
- "bab" (subsequence of "bbcbaba")
- "aba" (subsequence of "bbcbaba")

Constraints:

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

Solution: Enumerate first character of a palindrome

For a length 3 palindrome, we just need to enumerate the first character c.
We found the first and last occurrence of c in original string and scan the middle part to see how many unique characters there.

e.g. aabca
Enumerate from a to z, looking for a*a, b*b, …, z*z.
For a*a, aabca, we found first and last a, in between is abc, which has 3 unique letters.
We can use a hastable or a bitset to track unique letters.

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

C++

// Author: Huahua

class Solution {

public:

int countPalindromicSubsequence(string s) {

auto count = [&](char c) -> int {

int l = s.find_first_of(c);

int r = s.find_last_of(c);

if (l == string::npos || r == string::npos) return 0;

bitset<26> m;

for (int i = l + 1; i < r; ++i)

m.set(s[i] - 'a');

return m.count();

};

int ans = 0;

for (char c = 'a'; c <= 'z'; ++c)

ans += count(c);

return ans;

}

};

花花酱 LeetCode 2115. Find All Possible Recipes from Given Supplies

By zxi on December 26, 2021

You have information about n different recipes. You are given a string array recipes and a 2D string array ingredients. The i^th recipe has the name recipes[i], and you can create it if you have all the needed ingredients from ingredients[i]. Ingredients to a recipe may need to be created from other recipes, i.e., ingredients[i] may contain a string that is in recipes.

You are also given a string array supplies containing all the ingredients that you initially have, and you have an infinite supply of all of them.

Return a list of all the recipes that you can create. You may return the answer in any order.

Note that two recipes may contain each other in their ingredients.

Example 1:

Input: recipes = ["bread"], ingredients = [["yeast","flour"]], supplies = ["yeast","flour","corn"]
Output: ["bread"]
Explanation:
We can create "bread" since we have the ingredients "yeast" and "flour".

Example 2:

Input: recipes = ["bread","sandwich"], ingredients = [["yeast","flour"],["bread","meat"]], supplies = ["yeast","flour","meat"]
Output: ["bread","sandwich"]
Explanation:
We can create "bread" since we have the ingredients "yeast" and "flour".
We can create "sandwich" since we have the ingredient "meat" and can create the ingredient "bread".

Example 3:

Input: recipes = ["bread","sandwich","burger"], ingredients = [["yeast","flour"],["bread","meat"],["sandwich","meat","bread"]], supplies = ["yeast","flour","meat"]
Output: ["bread","sandwich","burger"]
Explanation:
We can create "bread" since we have the ingredients "yeast" and "flour".
We can create "sandwich" since we have the ingredient "meat" and can create the ingredient "bread".
We can create "burger" since we have the ingredient "meat" and can create the ingredients "bread" and "sandwich".

Constraints:

n == recipes.length == ingredients.length
1 <= n <= 100
1 <= ingredients[i].length, supplies.length <= 100
1 <= recipes[i].length, ingredients[i][j].length, supplies[k].length <= 10
recipes[i], ingredients[i][j], and supplies[k] consist only of lowercase English letters.
All the values of recipes and supplies combined are unique.
Each ingredients[i] does not contain any duplicate values.

Solution: Brute Force

C++

// Author: Huahua

class Solution {

public:

vector<string> findAllRecipes(vector<string>& recipes, vector<vector<string>>& ingredients, vector<string>& supplies) {

const int n = recipes.size();

unordered_set<string> s(begin(supplies), end(supplies));

vector<string> ans;

vector<int> seen(n);

while (true) {

bool newSupply = false;

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

if (seen[i]) continue;

bool hasAll = true;

for (const string& ingredient : ingredients[i])

if (!s.count(ingredient)) {

hasAll = false;

break;

}

if (!hasAll) continue;

ans.push_back(recipes[i]);

seen[i] = 1;

s.insert(recipes[i]);

newSupply = true;

}

if (!newSupply) break;

}

return ans;

}

};

花花酱 LeetCode 1921. Eliminate Maximum Number of Monsters

By zxi on December 25, 2021

You are playing a video game where you are defending your city from a group of n monsters. You are given a 0-indexed integer array dist of size n, where dist[i] is the initial distance in kilometers of the i^th monster from the city.

The monsters walk toward the city at a constant speed. The speed of each monster is given to you in an integer array speed of size n, where speed[i] is the speed of the i^th monster in kilometers per minute.

You have a weapon that, once fully charged, can eliminate a single monster. However, the weapon takes one minute to charge.The weapon is fully charged at the very start.

You lose when any monster reaches your city. If a monster reaches the city at the exact moment the weapon is fully charged, it counts as a loss, and the game ends before you can use your weapon.

Return the maximum number of monsters that you can eliminate before you lose, or n if you can eliminate all the monsters before they reach the city.

Example 1:

Input: dist = [1,3,4], speed = [1,1,1]
Output: 3
Explanation:
In the beginning, the distances of the monsters are [1,3,4]. You eliminate the first monster.
After a minute, the distances of the monsters are [X,2,3]. You eliminate the second monster.
After a minute, the distances of the monsters are [X,X,2]. You eliminate the thrid monster.
All 3 monsters can be eliminated.

Example 2:

Input: dist = [1,1,2,3], speed = [1,1,1,1]
Output: 1
Explanation:
In the beginning, the distances of the monsters are [1,1,2,3]. You eliminate the first monster.
After a minute, the distances of the monsters are [X,0,1,2], so you lose.
You can only eliminate 1 monster.

Example 3:

Input: dist = [3,2,4], speed = [5,3,2]
Output: 1
Explanation:
In the beginning, the distances of the monsters are [3,2,4]. You eliminate the first monster.
After a minute, the distances of the monsters are [X,0,2], so you lose.
You can only eliminate 1 monster.

Constraints:

n == dist.length == speed.length
1 <= n <= 10⁵
1 <= dist[i], speed[i] <= 10⁵

Solution: Greedy

Sort by arrival time, and see how many we can eliminate.

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

C++

// Author: Huahua

class Solution {

public:

int eliminateMaximum(vector<int>& dist, vector<int>& speed) {

const int n = dist.size();

vector<int> t(n);

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

t[i] = (dist[i] + speed[i] - 1) / speed[i];

sort(begin(t), end(t));

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

if (t[i] <= i) return i;

return n;

}

};

花花酱 LeetCode 1910. Remove All Occurrences of a Substring

By zxi on December 24, 2021

Given two strings s and part, perform the following operation on s until all occurrences of the substring part are removed:

Find the leftmost occurrence of the substring part and remove it from s.

Return s after removing all occurrences of part.

A substring is a contiguous sequence of characters in a string.

Example 1:

Input: s = "daabcbaabcbc", part = "abc"
Output: "dab"
Explanation: The following operations are done:
- s = "daabcbaabcbc", remove "abc" starting at index 2, so s = "dabaabcbc".
- s = "dabaabcbc", remove "abc" starting at index 4, so s = "dababc".
- s = "dababc", remove "abc" starting at index 3, so s = "dab".
Now s has no occurrences of "abc".

Example 2:

Input: s = "axxxxyyyyb", part = "xy"
Output: "ab"
Explanation: The following operations are done:
- s = "axxxxyyyyb", remove "xy" starting at index 4 so s = "axxxyyyb".
- s = "axxxyyyb", remove "xy" starting at index 3 so s = "axxyyb".
- s = "axxyyb", remove "xy" starting at index 2 so s = "axyb".
- s = "axyb", remove "xy" starting at index 1 so s = "ab".
Now s has no occurrences of "xy".

Constraints:

1 <= s.length <= 1000
1 <= part.length <= 1000
s and part consists of lowercase English letters.

Solution: Simulation

Time complexity: O(n²/m)
Space complexity: O(n)

C++

// Author: Huahua

class Solution {

public:

string removeOccurrences(string s, string part) {

while (true) {

size_t i = s.find(part);

if (i == string::npos) break;

s.erase(i, part.size());

}

return s;

}

};

花花酱 LeetCode 1300. Sum of Mutated Array Closest to Target

By zxi on December 24, 2021

Given an integer array arr and a target value target, return the integer value such that when we change all the integers larger than value in the given array to be equal to value, the sum of the array gets as close as possible (in absolute difference) to target.

In case of a tie, return the minimum such integer.

Notice that the answer is not neccesarilly a number from arr.

Example 1:

Input: arr = [4,9,3], target = 10
Output: 3
Explanation: When using 3 arr converts to [3, 3, 3] which sums 9 and that's the optimal answer.

Example 2:

Input: arr = [2,3,5], target = 10
Output: 5

Example 3:

Input: arr = [60864,25176,27249,21296,20204], target = 56803
Output: 11361

Constraints:

1 <= arr.length <= 10⁴
1 <= arr[i], target <= 10⁵

Solution: Binary Search

Find the smallest number x s.t. sum of the mutated array is >= target. Answer must be either x or x – 1.

Note, the search range should be [0, max(arr))

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

C++

// Author: Huahua]

class Solution {

public:

int findBestValue(vector<int>& arr, int target) {

int l = 0;

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

int ans = 0;

auto sum = [&](int v) {

int ans = 0;

for (int x : arr)

ans += min(x, v);

return ans;

};

while (l < r) {

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

if (sum(m) >= target)

r = m;

else

l = m + 1;

}

return abs(sum(l) - target) < abs(sum(l - 1) - target) ? l : l - 1;

}

};