Posts published in “Hashtable”

花花酱 LeetCode 1941. Check if All Characters Have Equal Number of Occurrences

By zxi on December 31, 2021

Given a string s, return true if s is a good string, or false otherwise.

A string s is good if all the characters that appear in s have the same number of occurrences (i.e., the same frequency).

Example 1:

Input: s = "abacbc"
Output: true
Explanation: The characters that appear in s are 'a', 'b', and 'c'. All characters occur 2 times in s.

Example 2:

Input: s = "aaabb"
Output: false
Explanation: The characters that appear in s are 'a' and 'b'.
'a' occurs 3 times while 'b' occurs 2 times, which is not the same number of times.

Constraints:

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

Solution: Hashtable

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

C++

// Author: Huahua

class Solution {

public:

bool areOccurrencesEqual(string s) {

vector<int> m(26);

int maxCount = 0;

for (char c : s)

maxCount = max(maxCount, ++m[c - 'a']);

return all_of(begin(m), end(m), [maxCount](int c) -> bool {

return c == 0 || c == maxCount;

});

}

};

Python3

# Author: Huahua

class Solution:

def areOccurrencesEqual(self, s: str) -> bool:

return len(set(Counter(s).values())) == 1

花花酱 LeetCode 1935. Maximum Number of Words You Can Type

By zxi on December 31, 2021

There is a malfunctioning keyboard where some letter keys do not work. All other keys on the keyboard work properly.

Given a string text of words separated by a single space (no leading or trailing spaces) and a string brokenLetters of all distinct letter keys that are broken, return the number of words in text you can fully type using this keyboard.

Example 1:

Input: text = "hello world", brokenLetters = "ad"
Output: 1
Explanation: We cannot type "world" because the 'd' key is broken.

Example 2:

Input: text = "leet code", brokenLetters = "lt"
Output: 1
Explanation: We cannot type "leet" because the 'l' and 't' keys are broken.

Example 3:

Input: text = "leet code", brokenLetters = "e"
Output: 0
Explanation: We cannot type either word because the 'e' key is broken.

Constraints:

1 <= text.length <= 10⁴
0 <= brokenLetters.length <= 26
text consists of words separated by a single space without any leading or trailing spaces.
Each word only consists of lowercase English letters.
brokenLetters consists of distinct lowercase English letters.

Solution: Hashset / bitset

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

C++

// Author: Huahua

class Solution {

public:

int canBeTypedWords(string text, string brokenLetters) {

const int n = text.size();

bitset<26> b;

for (char c : brokenLetters) b.set(c - 'a');

int ans = 0;

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

if (i == n || text[i] == ' ') {

if (!broken) ++ans;

broken = 0;

} else {

broken |= b[text[i] - 'a'];

}

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 2122. Recover the Original Array

By zxi on December 26, 2021

Alice had a 0-indexed array arr consisting of n positive integers. She chose an arbitrary positive integer k and created two new 0-indexed integer arrays lower and higher in the following manner:

lower[i] = arr[i] - k, for every index i where 0 <= i < n
higher[i] = arr[i] + k, for every index i where 0 <= i < n

Unfortunately, Alice lost all three arrays. However, she remembers the integers that were present in the arrays lower and higher, but not the array each integer belonged to. Help Alice and recover the original array.

Given an array nums consisting of 2n integers, where exactly n of the integers were present in lower and the remaining in higher, return the original array arr. In case the answer is not unique, return any valid array.

Note: The test cases are generated such that there exists at least one valid array arr.

Example 1:

Input: nums = [2,10,6,4,8,12]
Output: [3,7,11]
Explanation:
If arr = [3,7,11] and k = 1, we get lower = [2,6,10] and higher = [4,8,12].
Combining lower and higher gives us [2,6,10,4,8,12], which is a permutation of nums.
Another valid possibility is that arr = [5,7,9] and k = 3. In that case, lower = [2,4,6] and higher = [8,10,12].

Example 2:

Input: nums = [1,1,3,3]
Output: [2,2]
Explanation:
If arr = [2,2] and k = 1, we get lower = [1,1] and higher = [3,3].
Combining lower and higher gives us [1,1,3,3], which is equal to nums.
Note that arr cannot be [1,3] because in that case, the only possible way to obtain [1,1,3,3] is with k = 0.
This is invalid since k must be positive.

Example 3:

Input: nums = [5,435]
Output: [220]
Explanation:
The only possible combination is arr = [220] and k = 215. Using them, we get lower = [5] and higher = [435].

Constraints:

2 * n == nums.length
1 <= n <= 1000
1 <= nums[i] <= 10⁹
The test cases are generated such that there exists at least one valid array arr.

Solution: Try all possible k

Sort the array, we know that the smallest number nums[0] is org[0] – k, org[0] + k (nums[0] + 2k) must exist in nums. We try all possible ks. k = (nums[i] – nums[0]) / 2.

Then we iterate the sorted nums array as low, and see whether we can find low + 2k as high using a dynamic hashtable.

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

C++

// Author: Huahua

class Solution {

public:

vector<int> recoverArray(vector<int>& nums) {

const int n = nums.size();

sort(begin(nums), end(nums));

unordered_map<int, int> m;

for (int x : nums) ++m[x];

auto check = [&](int k) -> vector<int> {

vector<int> ans;

unordered_map<int, int> cur(m);

for (int x : nums) {

if (cur[x] == 0) continue;

--cur[x];

if (--cur[x + 2 * k] < 0) return {};

ans.push_back(x + k);

}

return ans;

};

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

if (nums[i] == nums[0] || (nums[i] - nums[0]) & 1) continue;

const int k = (nums[i] - nums[0]) / 2;

vector<int> ans = check(k);

if (!ans.empty()) return ans;

}

return {};

}

};

花花酱 LeetCode 2121. Intervals Between Identical Elements

By zxi on December 26, 2021

You are given a 0-indexed array of n integers arr.

The interval between two elements in arr is defined as the absolute difference between their indices. More formally, the interval between arr[i] and arr[j] is |i - j|.

Return an array intervals of length n where intervals[i] is the sum of intervals between arr[i] and each element in arr with the same value as arr[i].

Note: |x| is the absolute value of x.

Example 1:

Input: arr = [2,1,3,1,2,3,3]
Output: [4,2,7,2,4,4,5]
Explanation:
- Index 0: Another 2 is found at index 4. |0 - 4| = 4
- Index 1: Another 1 is found at index 3. |1 - 3| = 2
- Index 2: Two more 3s are found at indices 5 and 6. |2 - 5| + |2 - 6| = 7
- Index 3: Another 1 is found at index 1. |3 - 1| = 2
- Index 4: Another 2 is found at index 0. |4 - 0| = 4
- Index 5: Two more 3s are found at indices 2 and 6. |5 - 2| + |5 - 6| = 4
- Index 6: Two more 3s are found at indices 2 and 5. |6 - 2| + |6 - 5| = 5

Example 2:

Input: arr = [10,5,10,10]
Output: [5,0,3,4]
Explanation:
- Index 0: Two more 10s are found at indices 2 and 3. |0 - 2| + |0 - 3| = 5
- Index 1: There is only one 5 in the array, so its sum of intervals to identical elements is 0.
- Index 2: Two more 10s are found at indices 0 and 3. |2 - 0| + |2 - 3| = 3
- Index 3: Two more 10s are found at indices 0 and 2. |3 - 0| + |3 - 2| = 4

Constraints:

n == arr.length
1 <= n <= 10⁵
1 <= arr[i] <= 10⁵

Solution: Math / Hashtable + Prefix Sum

For each arr[i], suppose it occurs in the array of total c times, among which k of them are in front of it and c – k – 1 of them are after it. Then the total sum intervals:
(i – j₁) + (i – j₂) + … + (i – j_k) + (j_k+1-i) + (j_k+2-i) + … + (j_c-i)
<=> k * i – sum(j₁~j_k) + sum(j_k+1~j_c) – (c – k – 1) * i

Use a hashtable to store the indies of each unique number in the array and compute the prefix sum for fast range sum query.

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

C++

// Author: Huahua

class Solution {

public:

vector<long long> getDistances(vector<int>& arr) {

const int n = arr.size();

unordered_map<int, vector<long long>> m;

vector<int> pos(n);

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

m[arr[i]].push_back(i);

pos[i] = m[arr[i]].size() - 1;

}

for (auto& [k, idx] : m)

partial_sum(begin(idx), end(idx), begin(idx));

vector<long long> ans(n);

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

const auto& sums = m[arr[i]];

const long long k = pos[i];

const long long c = sums.size();

if (k > 0) ans[i] += k * i - sums[k - 1];

if (k + 1 < c) ans[i] += (sums[c - 1] - sums[k]) - (c - k - 1) * i;

}

return ans;

}

};