Huahua’s Tech Road

花花酱 LeetCode 2227. Encrypt and Decrypt Strings

By zxi on April 3, 2022

You are given a character array keys containing unique characters and a string array values containing strings of length 2. You are also given another string array dictionary that contains all permitted original strings after decryption. You should implement a data structure that can encrypt or decrypt a 0-indexed string.

A string is encrypted with the following process:

For each character c in the string, we find the index i satisfying keys[i] == c in keys.
Replace c with values[i] in the string.

A string is decrypted with the following process:

For each substring s of length 2 occurring at an even index in the string, we find an i such that values[i] == s. If there are multiple valid i, we choose any one of them. This means a string could have multiple possible strings it can decrypt to.
Replace s with keys[i] in the string.

Implement the Encrypter class:

Encrypter(char[] keys, String[] values, String[] dictionary) Initializes the Encrypter class with keys, values, and dictionary.
String encrypt(String word1) Encrypts word1 with the encryption process described above and returns the encrypted string.
int decrypt(String word2) Returns the number of possible strings word2 could decrypt to that also appear in dictionary.

Example 1:

Input
["Encrypter", "encrypt", "decrypt"]
[[['a', 'b', 'c', 'd'], ["ei", "zf", "ei", "am"], ["abcd", "acbd", "adbc", "badc", "dacb", "cadb", "cbda", "abad"]], ["abcd"], ["eizfeiam"]]
Output

[null, “eizfeiam”, 2]

Explanation Encrypter encrypter = new Encrypter([[‘a’, ‘b’, ‘c’, ‘d’], [“ei”, “zf”, “ei”, “am”], [“abcd”, “acbd”, “adbc”, “badc”, “dacb”, “cadb”, “cbda”, “abad”]); encrypter.encrypt(“abcd”); // return “eizfeiam”. // ‘a’ maps to “ei”, ‘b’ maps to “zf”, ‘c’ maps to “ei”, and ‘d’ maps to “am”. encrypter.decrypt(“eizfeiam”); // return 2. // “ei” can map to ‘a’ or ‘c’, “zf” maps to ‘b’, and “am” maps to ‘d’. // Thus, the possible strings after decryption are “abad”, “cbad”, “abcd”, and “cbcd”. // 2 of those strings, “abad” and “abcd”, appear in dictionary, so the answer is 2.

Constraints:

1 <= keys.length == values.length <= 26
values[i].length == 2
1 <= dictionary.length <= 100
1 <= dictionary[i].length <= 100
All keys[i] and dictionary[i] are unique.
1 <= word1.length <= 2000
1 <= word2.length <= 200
All word1[i] appear in keys.
word2.length is even.
keys, values[i], dictionary[i], word1, and word2 only contain lowercase English letters.
At most 200 calls will be made to encrypt and decrypt in total.

Solution:

For encryption, follow the instruction. Time complexity: O(len(word)) = O(2000)
For decryption, try all words in the dictionary and encrypt them and compare the encrypted string with the word to decrypt. Time complexity: O(sum(len(word_in_dict))) = O(100*100)

Worst case: 200 calls to decryption, T = 200 * O(100 * 100) = O(2*10⁶)

C++

// Author: Huahua

class Encrypter {

public:

Encrypter(vector<char>& keys,

vector<string>& values,

vector<string>& dictionary):

vals(26),

dict(dictionary) {

for (size_t i = 0; i < keys.size(); ++i)

vals[keys[i] - 'a'] = values[i];

}

string encrypt(string word1) {

string ans;

for (char c : word1)

ans += vals[c - 'a'];

return ans;

}

int decrypt(string word2) {

return count_if(begin(dict), end(dict), [&](const string& w){

return encrypt(w) == word2;

});

}

private:

vector<string> vals;

vector<string> dict;

};

Optimization

Pre-compute answer for all the words in dictionary.

decrypt: Time complexity: O(1)

C++

// Author: Huahua

class Encrypter {

public:

Encrypter(vector<char>& keys,

vector<string>& values,

vector<string>& dictionary):

vals(26) {

for (size_t i = 0; i < keys.size(); ++i)

vals[keys[i] - 'a'] = values[i];

for (const string& w : dictionary)

++counts[encrypt(w)];

}

string encrypt(string word1) {

string ans;

for (char c : word1)

ans += vals[c - 'a'];

return ans;

}

int decrypt(string word2) {

auto it = counts.find(word2);

return it == counts.end() ? 0 : it->second;

}

private:

vector<string> vals;

unordered_map<string, int> counts;

};

花花酱 LeetCode 2226. Maximum Candies Allocated to K Children

By zxi on April 2, 2022

You are given a 0-indexed integer array candies. Each element in the array denotes a pile of candies of size candies[i]. You can divide each pile into any number of sub piles, but you cannot merge two piles together.

You are also given an integer k. You should allocate piles of candies to k children such that each child gets the same number of candies. Each child can take at most one pile of candies and some piles of candies may go unused.

Return the maximum number of candies each child can get.

Example 1:

Input: candies = [5,8,6], k = 3
Output: 5
Explanation: We can divide candies[1] into 2 piles of size 5 and 3, and candies[2] into 2 piles of size 5 and 1. We now have five piles of candies of sizes 5, 5, 3, 5, and 1. We can allocate the 3 piles of size 5 to 3 children. It can be proven that each child cannot receive more than 5 candies.

Example 2:

Input: candies = [2,5], k = 11
Output: 0
Explanation: There are 11 children but only 7 candies in total, so it is impossible to ensure each child receives at least one candy. Thus, each child gets no candy and the answer is 0.

Constraints:

1 <= candies.length <= 10⁵
1 <= candies[i] <= 10⁷
1 <= k <= 10¹²

Solution: Binary Search

Find the smallest L s.t. we can allocate candies to less than k children.

ans = L – 1.

Time complexity: O(nlogm) where n is number of piles, m is sum(candies) / k.
Space complexity: O(1)

C++

// Author: Huahua

class Solution {

public:

int maximumCandies(vector<int>& candies, long long k) {

long long total = accumulate(begin(candies), end(candies), 0LL);

long long l = 1;

long long r = total / k + 1;

while (l < r) {

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

long long c = 0;

for (int pile : candies)

c += pile / m;

if (c < k)

r = m;

else

l = m + 1;

}

return l - 1;

}

};

花花酱 LeetCode 2225. Find Players With Zero or One Losses

By zxi on April 2, 2022

You are given an integer array matches where matches[i] = [winner_i, loser_i] indicates that the player winner_i defeated player loser_i in a match.

Return a list answer of size 2 where:

answer[0] is a list of all players that have not lost any matches.
answer[1] is a list of all players that have lost exactly one match.

The values in the two lists should be returned in increasing order.

Note:

You should only consider the players that have played at least one match.
The testcases will be generated such that no two matches will have the same outcome.

Example 1:

Input: matches = [[1,3],[2,3],[3,6],[5,6],[5,7],[4,5],[4,8],[4,9],[10,4],[10,9]]
Output: [[1,2,10],[4,5,7,8]]
Explanation:
Players 1, 2, and 10 have not lost any matches.
Players 4, 5, 7, and 8 each have lost one match.
Players 3, 6, and 9 each have lost two matches.
Thus, answer[0] = [1,2,10] and answer[1] = [4,5,7,8].

Example 2:

Input: matches = [[2,3],[1,3],[5,4],[6,4]]
Output: [[1,2,5,6],[]]
Explanation:
Players 1, 2, 5, and 6 have not lost any matches.
Players 3 and 4 each have lost two matches.
Thus, answer[0] = [1,2,5,6] and answer[1] = [].

Constraints:

1 <= matches.length <= 10⁵
matches[i].length == 2
1 <= winner_i, loser_i <= 10⁵
winner_i != loser_i
All matches[i] are unique.

Solution: Hashtable

Use a hashtable to store the number of matches each player has lost. Note, also create an entry for those winners who never lose.

Time complexity: O(m), m = # of matches
Space complexity: O(n), n = # of players

C++

// Author: Huahua

class Solution {

public:

vector<vector<int>> findWinners(vector<vector<int>>& matches) {

unordered_map<int, int> m;

for (const auto& match : matches) {

m[match[0]]; // create an entry for the winner.

++m[match[1]];

}

vector<vector<int>> ans(2);

for (const auto& [player, loses] : m)

if (loses <= 1) ans[loses].push_back(player);

sort(begin(ans[0]), end(ans[0]));

sort(begin(ans[1]), end(ans[1]));

return ans;

}

};

花花酱 LeetCode 2224. Minimum Number of Operations to Convert Time

By zxi on April 2, 2022

You are given two strings current and correct representing two 24-hour times.

24-hour times are formatted as "HH:MM", where HH is between 00 and 23, and MM is between 00 and 59. The earliest 24-hour time is 00:00, and the latest is 23:59.

In one operation you can increase the time current by 1, 5, 15, or 60 minutes. You can perform this operation any number of times.

Return the minimum number of operations needed to convert current to correct.

Example 1:

Input: current = "02:30", correct = "04:35"
Output: 3
Explanation:
We can convert current to correct in 3 operations as follows:
- Add 60 minutes to current. current becomes "03:30".
- Add 60 minutes to current. current becomes "04:30".
- Add 5 minutes to current. current becomes "04:35".
It can be proven that it is not possible to convert current to correct in fewer than 3 operations.

Example 2:

Input: current = "11:00", correct = "11:01"
Output: 1
Explanation: We only have to add one minute to current, so the minimum number of operations needed is 1.

Constraints:

current and correct are in the format "HH:MM"
current <= correct

Solution: Greedy

Start with 60, then 15, 5 and finally increase 1 minute a time.

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

C++

// Author: Huahua

class Solution {

public:

int convertTime(string current, string correct) {

auto getMinute = [](string_view t) {

return (t[0] - '0') * 10 * 60

+ (t[1] - '0') * 60

+ (t[3] - '0') * 10

+ (t[4] - '0');

};

int t1 = getMinute(current);

int t2 = getMinute(correct);

int ans = 0;

for (int d : {60, 15, 5, 1})

while (t2 - t1 >= d) {

++ans;

t1 += d;

}

return ans;

}

};

花花酱 LeetCode 2223. Sum of Scores of Built Strings

By zxi on April 2, 2022

You are building a string s of length n one character at a time, prepending each new character to the front of the string. The strings are labeled from 1 to n, where the string with length i is labeled s_i.

For example, for s = "abaca", s₁ == "a", s₂ == "ca", s₃ == "aca", etc.

The score of s_i is the length of the longest common prefix between s_i and s_n (Note that s == s_n).

Given the final string s, return the sum of the score of every s_i.

Example 1:

Input: s = "babab"
Output: 9
Explanation:
For s₁ == "b", the longest common prefix is "b" which has a score of 1.
For s₂ == "ab", there is no common prefix so the score is 0.
For s₃ == "bab", the longest common prefix is "bab" which has a score of 3.
For s₄ == "abab", there is no common prefix so the score is 0.
For s₅ == "babab", the longest common prefix is "babab" which has a score of 5.
The sum of the scores is 1 + 0 + 3 + 0 + 5 = 9, so we return 9.

Example 2:

Input: s = "azbazbzaz"
Output: 14
Explanation: 
For s₂ == "az", the longest common prefix is "az" which has a score of 2.
For s₆ == "azbzaz", the longest common prefix is "azb" which has a score of 3.
For s₉ == "azbazbzaz", the longest common prefix is "azbazbzaz" which has a score of 9.
For all other s_i, the score is 0.
The sum of the scores is 2 + 3 + 9 = 14, so we return 14.

Constraints:

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

Solution: Z-Function

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

C++

// Author: Huahua

class Solution {

public:

long long sumScores(string s) {

auto zFunc = [](string_view s) {

const int n = s.length();

vector<long long> z(n);

for (long long i = 1, l = 0, r = 0; i < n; ++i) {

if (i <= r)

z[i] = min(r - i + 1, z[i - l]);

while (i + z[i] < n && s[z[i]] == s[i + z[i]])

++z[i];

if (i + z[i] - 1 > r) {

l = i;

r = i + z[i] - 1;

}

return accumulate(begin(z), end(z), 0LL);

};

return zFunc(s) + s.length();

}

};

Huahua's Tech Road

花花酱 LeetCode 2227. Encrypt and Decrypt Strings

Solution:

C++

Optimization

C++

花花酱 LeetCode 2226. Maximum Candies Allocated to K Children

Solution: Binary Search

C++

花花酱 LeetCode 2225. Find Players With Zero or One Losses

Solution: Hashtable

C++

花花酱 LeetCode 2224. Minimum Number of Operations to Convert Time

Solution: Greedy

C++

花花酱 LeetCode 2223. Sum of Scores of Built Strings

Solution: Z-Function

C++