Posts published in “Hashtable”

花花酱 LeetCode 2131. Longest Palindrome by Concatenating Two Letter Words

By zxi on January 9, 2022

You are given an array of strings words. Each element of words consists of two lowercase English letters.

Create the longest possible palindrome by selecting some elements from words and concatenating them in any order. Each element can be selected at most once.

Return the length of the longest palindrome that you can create. If it is impossible to create any palindrome, return 0.

A palindrome is a string that reads the same forward and backward.

Example 1:

Input: words = ["lc","cl","gg"]
Output: 6
Explanation: One longest palindrome is "lc" + "gg" + "cl" = "lcggcl", of length 6.
Note that "clgglc" is another longest palindrome that can be created.

Example 2:

Input: words = ["ab","ty","yt","lc","cl","ab"]
Output: 8
Explanation: One longest palindrome is "ty" + "lc" + "cl" + "yt" = "tylcclyt", of length 8.
Note that "lcyttycl" is another longest palindrome that can be created.

Example 3:

Input: words = ["cc","ll","xx"]
Output: 2
Explanation: One longest palindrome is "cc", of length 2.
Note that "ll" is another longest palindrome that can be created, and so is "xx".

Constraints:

1 <= words.length <= 10⁵
words[i].length == 2
words[i] consists of lowercase English letters.

Solution: Match mirrored words

For any pair of mirrored words, e.g. ‘ab’ <-> ‘ba’ or ‘aa’ <-> ‘aa’, we can extend the existing longest palindrome, ans += 4.
For any unpaired words with same letter, e.g. ‘cc’, we can only use one and put in the middle of the pladrome, ans += 2.

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

C++

// Author: Huahua

class Solution {

public:

int longestPalindrome(vector<string>& words) {

int ans = 0;

int same = 0;

vector<vector<int>> m(26, vector<int>(26));

for (const string& word : words) {

const int a = word[0] - 'a';

const int b = word[1] - 'a';

if (m[b][a]) {

--m[b][a];

ans += 4;

} else {

++m[a][b];

}

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

if (m[i][i]) {

ans += 2;

break;

}

return ans;

}

};

花花酱 LeetCode 1995. Count Special Quadruplets

By zxi on December 31, 2021

Given a 0-indexed integer array nums, return the number of distinct quadruplets (a, b, c, d) such that:

nums[a] + nums[b] + nums[c] == nums[d], and
a < b < c < d

Example 1:

Input: nums = [1,2,3,6]
Output: 1
Explanation: The only quadruplet that satisfies the requirement is (0, 1, 2, 3) because 1 + 2 + 3 == 6.

Example 2:

Input: nums = [3,3,6,4,5]
Output: 0
Explanation: There are no such quadruplets in [3,3,6,4,5].

Example 3:

Input: nums = [1,1,1,3,5]
Output: 4
Explanation: The 4 quadruplets that satisfy the requirement are:
- (0, 1, 2, 3): 1 + 1 + 1 == 3
- (0, 1, 3, 4): 1 + 1 + 3 == 5
- (0, 2, 3, 4): 1 + 1 + 3 == 5
- (1, 2, 3, 4): 1 + 1 + 3 == 5

Constraints:

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

Solution 1: Brute force (224ms)

Enumerate a, b, c, d.

Time complexity: O(C(n, 4)) = O(n⁴/24)
Space complexity: O(1)

C++

// Author: Huahua

class Solution {

public:

int countQuadruplets(vector<int>& nums) {

const int n = nums.size();

int ans = 0;

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

for (int b = a + 1; b < n; ++b)

for (int c = b + 1; c < n; ++c)

for (int d = c + 1; d < n; ++d)

ans += nums[a] + nums[b] + nums[c] == nums[d];

return ans;

}

};

Solution 2: Static frequency table + binary search (39ms)

For each element, we store its indices (sorted).

Given a, b, c, target t = nums[a] + nums[b] + nums[c], we check the hashtable and use binary search to find how many times it occurred after index c.

Time complexity: O(n³/6*logn)
Space complexity: O(n)

C++

// Author: Huahua

class Solution {

public:

int countQuadruplets(vector<int>& nums) {

constexpr int kMax = 100;

const int n = nums.size();

int ans = 0;

vector<vector<int>> m(kMax + 1);

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

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

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

for (int b = a + 1; b < n; ++b)

for (int c = b + 1; c < n; ++c) {

const int t = nums[a] + nums[b] + nums[c];

if (t > kMax) continue;

ans += end(m[t]) - lower_bound(begin(m[t]), end(m[t]), c + 1);

}

return ans;

}

};

Solution 3: Dynamic frequency table (29ms)

Similar to 花花酱 LeetCode 1. Two Sum, we dynamically add elements (from right to left) into the hashtable.

Time complexity: O(n³/6)
Space complexity: O(n)

C++

// Author: Huahua

class Solution {

public:

int countQuadruplets(vector<int>& nums) {

constexpr int kMax = 100;

const int n = nums.size();

int ans = 0;

vector<int> m(kMax + 1);

// for every c we had seen, we can use it as target (nums[d]).

for (int c = n - 1; c >= 0; ++m[nums[c--]])

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

for (int b = a + 1; b < c; ++b) {

const int t = nums[a] + nums[b] + nums[c];

if (t > kMax) continue;

ans += m[t];

}

return ans;

}

};

花花酱 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;

}

};