Posts tagged as “medium”

花花酱 LeetCode 3319. K-th Largest Perfect Subtree Size in Binary Tree

By zxi on October 12, 2024

You are given the root of a binary tree and an integer k.

Return an integer denoting the size of the k^th largest perfect binary

subtree, or -1 if it doesn’t exist.

A perfect binary tree is a tree where all leaves are on the same level, and every parent has two children.

Example 1:

Input: root = [5,3,6,5,2,5,7,1,8,null,null,6,8], k = 2

Output: 3

Explanation:

The roots of the perfect binary subtrees are highlighted in black. Their sizes, in decreasing order are [3, 3, 1, 1, 1, 1, 1, 1].
The 2^nd largest size is 3.

Example 2:

Input: root = [1,2,3,4,5,6,7], k = 1

Output: 7

Explanation:

The sizes of the perfect binary subtrees in decreasing order are [7, 3, 3, 1, 1, 1, 1]. The size of the largest perfect binary subtree is 7.

Example 3:

Input: root = [1,2,3,null,4], k = 3

Output: -1

Explanation:

The sizes of the perfect binary subtrees in decreasing order are [1, 1]. There are fewer than 3 perfect binary subtrees.

Constraints:

The number of nodes in the tree is in the range [1, 2000].
1 <= Node.val <= 2000
1 <= k <= 1024

Solution: DFS

Write a function f() to return the perfect subtree size at node n.

def f(TreeNode n):
if not n: return 0
l, r = f(n.left), f(n.right)
return l + r + 1 if l == r && l != -1 else -1

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

class Solution {

public:

int kthLargestPerfectSubtree(TreeNode* root, int k) {

vector<int> ss;

function<int(TreeNode*)> PerfectSubtree = [&](TreeNode* node) -> int {

if (node == nullptr) return 0;

int l = PerfectSubtree(node->left);

int r = PerfectSubtree(node->right);

if (l == r && l != -1) {

ss.push_back(l + r + 1);

return ss.back();

}

return -1;

};

PerfectSubtree(root);

sort(rbegin(ss), rend(ss));

return k <= ss.size() ? ss[k - 1] : -1;

}

};

花花酱 LeetCode 3029. Minimum Time to Revert Word to Initial State I

By zxi on February 5, 2024

You are given a 0-indexed string word and an integer k.

At every second, you must perform the following operations:

Remove the first k characters of word.
Add any k characters to the end of word.

Note that you do not necessarily need to add the same characters that you removed. However, you must perform both operations at every second.

Return the minimum time greater than zero required for word to revert to its initial state.

Example 1:

Input: word = "abacaba", k = 3
Output: 2
Explanation: At the 1st second, we remove characters "aba" from the prefix of word, and add characters "bac" to the end of word. Thus, word becomes equal to "cababac".
At the 2nd second, we remove characters "cab" from the prefix of word, and add "aba" to the end of word. Thus, word becomes equal to "abacaba" and reverts to its initial state.
It can be shown that 2 seconds is the minimum time greater than zero required for word to revert to its initial state.

Example 2:

Input: word = "abacaba", k = 4
Output: 1
Explanation: At the 1st second, we remove characters "abac" from the prefix of word, and add characters "caba" to the end of word. Thus, word becomes equal to "abacaba" and reverts to its initial state.
It can be shown that 1 second is the minimum time greater than zero required for word to revert to its initial state.

Example 3:

Input: word = "abcbabcd", k = 2
Output: 4
Explanation: At every second, we will remove the first 2 characters of word, and add the same characters to the end of word.
After 4 seconds, word becomes equal to "abcbabcd" and reverts to its initial state.
It can be shown that 4 seconds is the minimum time greater than zero required for word to revert to its initial state.

Constraints:

1 <= word.length <= 50
1 <= k <= word.length
word consists only of lowercase English letters.

Solution: Suffix ==? Prefix

Compare the suffix with prefix.

word = “abacaba”, k = 3
ans = 1, “~~aba~~caba” != “abac~~aba~~“
ans = 2, “~~abacab~~a” == “a~~bacaba~~“, we find it.

Time complexity: O(n * n / k)
Space complexity: O(1)

C++

class Solution {

public:

int minimumTimeToInitialState(string_view word, int k) {

const int n = word.length();

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

string_view t = word.substr(i * k);

if (t == word.substr(0, t.length())) return i;

}

return (n + k - 1) / k;

}

};

花花酱 LeetCode 2976. Minimum Cost to Convert String I

By zxi on January 8, 2024

You are given two 0-indexed strings source and target, both of length n and consisting of lowercase English letters. You are also given two 0-indexed character arrays original and changed, and an integer array cost, where cost[i] represents the cost of changing the character original[i] to the character changed[i].

You start with the string source. In one operation, you can pick a character x from the string and change it to the character y at a cost of z if there exists any index j such that cost[j] == z, original[j] == x, and changed[j] == y.

Return the minimum cost to convert the string source to the string target using any number of operations. If it is impossible to convert source to target, return -1.

Note that there may exist indices i, j such that original[j] == original[i] and changed[j] == changed[i].

Example 1:

Input: source = "abcd", target = "acbe", original = ["a","b","c","c","e","d"], changed = ["b","c","b","e","b","e"], cost = [2,5,5,1,2,20]
Output: 28
Explanation: To convert the string "abcd" to string "acbe":
- Change value at index 1 from 'b' to 'c' at a cost of 5.
- Change value at index 2 from 'c' to 'e' at a cost of 1.
- Change value at index 2 from 'e' to 'b' at a cost of 2.
- Change value at index 3 from 'd' to 'e' at a cost of 20.
The total cost incurred is 5 + 1 + 2 + 20 = 28.
It can be shown that this is the minimum possible cost.

Example 2:

Input: source = "aaaa", target = "bbbb", original = ["a","c"], changed = ["c","b"], cost = [1,2]
Output: 12
Explanation: To change the character 'a' to 'b' change the character 'a' to 'c' at a cost of 1, followed by changing the character 'c' to 'b' at a cost of 2, for a total cost of 1 + 2 = 3. To change all occurrences of 'a' to 'b', a total cost of 3 * 4 = 12 is incurred.

Example 3:

Input: source = "abcd", target = "abce", original = ["a"], changed = ["e"], cost = [10000]
Output: -1
Explanation: It is impossible to convert source to target because the value at index 3 cannot be changed from 'd' to 'e'.

Constraints:

1 <= source.length == target.length <= 10⁵
source, target consist of lowercase English letters.
1 <= cost.length == original.length == changed.length <= 2000
original[i], changed[i] are lowercase English letters.
1 <= cost[i] <= 10⁶
original[i] != changed[i]

Solution: All pairs shortest path

Compute the shortest path (min cost) for any given letter pairs.

Time complexity: O(26^3 + m + n)
Space complexity: O(26^2)

C++

class Solution {

public:

long long minimumCost(string s, string t, vector<char>& o, vector<char>& c, vector<int>& cost) {

const int n = c.size();

vector<vector<int>> d(26, vector<int>(26, 1e9));

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

d[i][i] = 0;

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

d[o[i] - 'a'][c[i] - 'a'] = min(d[o[i] - 'a'][c[i] - 'a'], cost[i]);

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

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

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

if (d[i][k] + d[k][j] < d[i][j])

d[i][j] = d[i][k] + d[k][j];

long ans = 0;

for (int i = 0; i < s.size(); ++i) {

if (d[s[i] - 'a'][t[i] - 'a'] >= 1e9) return -1;

ans += d[s[i] - 'a'][t[i] - 'a'];

}

return ans;

}

};

花花酱 LeetCode 2829. Determine the Minimum Sum of a k-avoiding Array

By zxi on August 26, 2023

You are given two integers, n and k.

An array of distinct positive integers is called a k-avoiding array if there does not exist any pair of distinct elements that sum to k.

Return the minimum possible sum of a k-avoiding array of length n.

Example 1:

Input: n = 5, k = 4
Output: 18
Explanation: Consider the k-avoiding array [1,2,4,5,6], which has a sum of 18.
It can be proven that there is no k-avoiding array with a sum less than 18.

Example 2:

Input: n = 2, k = 6
Output: 3
Explanation: We can construct the array [1,2], which has a sum of 3.
It can be proven that there is no k-avoiding array with a sum less than 3.

Constraints:

1 <= n, k <= 50

Solution 1: Greedy + HashTable

Always choose the smallest possible number starting from 1.

Add all chosen numbers into a hashtable. For a new candidate i, check whether k – i is already in the hashtable.

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

C++

// Author: Huahua

class Solution {

public:

int minimumSum(int n, int k) {

int sum = 0;

unordered_set<int> s;

for (int i = 1; s.size() != n; ++i) {

if (s.count(k - i)) continue;

sum += i;

s.insert(i);

}

return sum;

}

};

花花酱 LeetCode 2825. Make String a Subsequence Using Cyclic Increments

By zxi on August 23, 2023

You are given two 0-indexed strings str1 and str2.

In an operation, you select a set of indices in str1, and for each index i in the set, increment str1[i] to the next character cyclically. That is 'a' becomes 'b', 'b' becomes 'c', and so on, and 'z' becomes 'a'.

Return true if it is possible to make str2 a subsequence of str1 by performing the operation at most once, and false otherwise.

Note: A subsequence of a string is a new string that is formed from the original string by deleting some (possibly none) of the characters without disturbing the relative positions of the remaining characters.

Example 1:

Input: str1 = "abc", str2 = "ad"
Output: true
Explanation: Select index 2 in str1.
Increment str1[2] to become 'd'. 
Hence, str1 becomes "abd" and str2 is now a subsequence. Therefore, true is returned.

Example 2:

Input: str1 = "zc", str2 = "ad"
Output: true
Explanation: Select indices 0 and 1 in str1. 
Increment str1[0] to become 'a'. 
Increment str1[1] to become 'd'. 
Hence, str1 becomes "ad" and str2 is now a subsequence. Therefore, true is returned.

Example 3:

Input: str1 = "ab", str2 = "d"
Output: false
Explanation: In this example, it can be shown that it is impossible to make str2 a subsequence of str1 using the operation at most once. 
Therefore, false is returned.

Constraints:

1 <= str1.length <= 10⁵
1 <= str2.length <= 10⁵
str1 and str2 consist of only lowercase English letters.

Solution: Two pointers

s1[i] and s2[j] can match if
s1[i] == s2[j] or inc(s1[i]) == s2[j]

If matched: ++i; ++j else ++i.

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

C++

class Solution {

public:

bool canMakeSubsequence(string_view s1, string_view s2) {

for (int i = 0, j = 0, n = s1.size(), m = s2.size(); i < n; ++i)

if (s1[i] == s2[j] || (s1[i] - 'a' + 1) % 26 == s2[j] - 'a')

if (++j == m) return true;

return false;

}

};

Iterator version

C++

class Solution {

public:

bool canMakeSubsequence(string_view s1, string_view s2) {

for (auto i = begin(s1), j = begin(s2); i != end(s1); ++i)

if (*i == *j || (*i - 'a' + 1) % 26 == *j - 'a')

if (++j == end(s2)) return true;

return false;

}

};