Huahua’s Tech Road

花花酱 LeetCode 2078. Two Furthest Houses With Different Colors

By zxi on November 20, 2021

There are n houses evenly lined up on the street, and each house is beautifully painted. You are given a 0-indexed integer array colors of length n, where colors[i] represents the color of the i^th house.

Return the maximum distance between two houses with different colors.

The distance between the i^th and j^th houses is abs(i - j), where abs(x) is the absolute value of x.

Example 1:

Input: colors = [1,1,1,6,1,1,1]
Output: 3
Explanation: In the above image, color 1 is blue, and color 6 is red.
The furthest two houses with different colors are house 0 and house 3.
House 0 has color 1, and house 3 has color 6. The distance between them is abs(0 - 3) = 3.
Note that houses 3 and 6 can also produce the optimal answer.

Example 2:

Input: colors = [1,8,3,8,3]
Output: 4
Explanation: In the above image, color 1 is blue, color 8 is yellow, and color 3 is green.
The furthest two houses with different colors are house 0 and house 4.
House 0 has color 1, and house 4 has color 3. The distance between them is abs(0 - 4) = 4.

Example 3:

Input: colors = [0,1]
Output: 1
Explanation: The furthest two houses with different colors are house 0 and house 1.
House 0 has color 0, and house 1 has color 1. The distance between them is abs(0 - 1) = 1.

Constraints:

n == colors.length
2 <= n <= 100
0 <= colors[i] <= 100
Test data are generated such that at least two houses have different colors.

Solution 1: Brute Force

Try all pairs.
Time complexity: O(n²)
Space complexity: O(1)

C++

// Author: Huahua

class Solution {

public:

int maxDistance(vector<int>& colors) {

const int n = colors.size();

for (int d = n - 1; d > 0; --d)

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

if (colors[i] != colors[i + d])

return d;

return 0;

}

};

Solution 2: Greedy / One pass

First house or last house must be involved in the ans.

Scan the house and check with first and last house.

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

C++

// Author: Huahua

class Solution {

public:

int maxDistance(vector<int>& colors) {

int ans = 0;

const int n = colors.size();

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

ans = max({ans,

i * (colors[i] != colors[0]),

(n - i - 1) * (colors[i] != colors[n - 1])});

return ans;

}

};

花花酱 LeetCode 2003. Smallest Missing Genetic Value in Each Subtree

By zxi on November 20, 2021

There is a family tree rooted at 0 consisting of n nodes numbered 0 to n - 1. You are given a 0-indexed integer array parents, where parents[i] is the parent for node i. Since node 0 is the root, parents[0] == -1.

There are 10⁵ genetic values, each represented by an integer in the inclusive range [1, 10⁵]. You are given a 0-indexed integer array nums, where nums[i] is a distinct genetic value for node i.

Return an array ans of length n where ans[i] is the smallest genetic value that is missing from the subtree rooted at node i.

The subtree rooted at a node x contains node x and all of its descendant nodes.

Example 1:

Input: parents = [-1,0,0,2], nums = [1,2,3,4]
Output: [5,1,1,1]
Explanation: The answer for each subtree is calculated as follows:
- 0: The subtree contains nodes [0,1,2,3] with values [1,2,3,4]. 5 is the smallest missing value.
- 1: The subtree contains only node 1 with value 2. 1 is the smallest missing value.
- 2: The subtree contains nodes [2,3] with values [3,4]. 1 is the smallest missing value.
- 3: The subtree contains only node 3 with value 4. 1 is the smallest missing value.

Example 2:

Input: parents = [-1,0,1,0,3,3], nums = [5,4,6,2,1,3]
Output: [7,1,1,4,2,1]
Explanation: The answer for each subtree is calculated as follows:
- 0: The subtree contains nodes [0,1,2,3,4,5] with values [5,4,6,2,1,3]. 7 is the smallest missing value.
- 1: The subtree contains nodes [1,2] with values [4,6]. 1 is the smallest missing value.
- 2: The subtree contains only node 2 with value 6. 1 is the smallest missing value.
- 3: The subtree contains nodes [3,4,5] with values [2,1,3]. 4 is the smallest missing value.
- 4: The subtree contains only node 4 with value 1. 2 is the smallest missing value.
- 5: The subtree contains only node 5 with value 3. 1 is the smallest missing value.

Example 3:

Input: parents = [-1,2,3,0,2,4,1], nums = [2,3,4,5,6,7,8]
Output: [1,1,1,1,1,1,1]
Explanation: The value 1 is missing from all the subtrees.

Constraints:

Solution: DFS on a single path

One ancestors of node with value of 1 will have missing values greater than 1. We do a dfs on the path that from node with value 1 to the root.

Time complexity: O(n + max(nums))
Space complexity: O(n + max(nums))

C++

// Author: Huahua

class Solution {

public:

vector<int> smallestMissingValueSubtree(vector<int>& parents, vector<int>& nums) {

const int n = parents.size();

vector<int> ans(n, 1);

vector<int> seen(100002);

vector<vector<int>> g(n);

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

g[parents[i]].push_back(i);

function<void(int)> dfs = [&](int u) {

if (seen[nums[u]]++) return;

for (int v : g[u]) dfs(v);

};

int u = find(begin(nums), end(nums), 1) - begin(nums);

for (int l = 1; u < n && u != -1; u = parents[u]) {

dfs(u);

while (seen[l]) ++l;

ans[u] = l;

}

return ans;

}

};

花花酱 LeetCode 2002. Maximum Product of the Length of Two Palindromic Subsequences

By zxi on November 20, 2021

Given a string s, find two disjoint palindromic subsequences of s such that the product of their lengths is maximized. The two subsequences are disjoint if they do not both pick a character at the same index.

Return the maximum possible product of the lengths of the two palindromic subsequences.

A subsequence is a string that can be derived from another string by deleting some or no characters without changing the order of the remaining characters. A string is palindromic if it reads the same forward and backward.

Example 1:

Input: s = "leetcodecom"
Output: 9
Explanation: An optimal solution is to choose "ete" for the 1^st subsequence and "cdc" for the 2^nd subsequence.
The product of their lengths is: 3 * 3 = 9.

Example 2:

Input: s = "bb"
Output: 1
Explanation: An optimal solution is to choose "b" (the first character) for the 1^st subsequence and "b" (the second character) for the 2^nd subsequence.
The product of their lengths is: 1 * 1 = 1.

Example 3:

Input: s = "accbcaxxcxx"
Output: 25
Explanation: An optimal solution is to choose "accca" for the 1^st subsequence and "xxcxx" for the 2^nd subsequence.
The product of their lengths is: 5 * 5 = 25.

Constraints:

2 <= s.length <= 12
s consists of lowercase English letters only.

Solution 1: DFS

Time complexity: O(3ⁿ*n)
Space complexity: O(n)

C++

// Author: Huahua

class Solution {

public:

int maxProduct(string s) {

auto isPalindrom = [](const string& s) {

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

if (s[i] != s[s.size() - i - 1]) return false;

return true;

};

const int n = s.size();

vector<string> ss(3);

size_t ans = 0;

function<void(int)> dfs = [&](int i) -> void {

if (i == n) {

if (isPalindrom(ss[0]) && isPalindrom(ss[1]))

ans = max(ans, ss[0].size() * ss[1].size());

return;

}

for (int k = 0; k < 3; ++k) {

ss[k].push_back(s[i]);

dfs(i + 1);

ss[k].pop_back();

}

};

dfs(0);

return ans;

}

};

Solution: Subsets + Bitmask + All Pairs

Time complexity: O(2²ⁿ)
Space complexity: O(2ⁿ)

C++

// Author: Huahua

class Solution {

public:

int maxProduct(string s) {

auto isPalindrom = [](const string& s) {

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

if (s[i] != s[s.size() - i - 1]) return false;

return true;

};

const int n = s.size();

unordered_set<int> p;

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

string t;

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

if (i >> j & 1) t.push_back(s[j]);

if (isPalindrom(t))

p.insert(i);

}

int ans = 0;

for (int s1 : p)

for (int s2 : p)

if (!(s1 & s2))

ans = max(ans, __builtin_popcount(s1) * __builtin_popcount(s2));

return ans;

}

};

花花酱 LeetCode 2001. Number of Pairs of Interchangeable Rectangles

By zxi on November 20, 2021

You are given n rectangles represented by a 0-indexed 2D integer array rectangles, where rectangles[i] = [width_i, height_i] denotes the width and height of the i^th rectangle.

Two rectangles i and j (i < j) are considered interchangeable if they have the same width-to-height ratio. More formally, two rectangles are interchangeable if width_i/height_i == width_j/height_j (using decimal division, not integer division).

Return the number of pairs of interchangeable rectangles in rectangles.

Example 1:

Input: rectangles = [[4,8],[3,6],[10,20],[15,30]]
Output: 6
Explanation: The following are the interchangeable pairs of rectangles by index (0-indexed):
- Rectangle 0 with rectangle 1: 4/8 == 3/6.
- Rectangle 0 with rectangle 2: 4/8 == 10/20.
- Rectangle 0 with rectangle 3: 4/8 == 15/30.
- Rectangle 1 with rectangle 2: 3/6 == 10/20.
- Rectangle 1 with rectangle 3: 3/6 == 15/30.
- Rectangle 2 with rectangle 3: 10/20 == 15/30.

Example 2:

Input: rectangles = [[4,5],[7,8]]
Output: 0
Explanation: There are no interchangeable pairs of rectangles.

Constraints:

n == rectangles.length
1 <= n <= 10⁵
rectangles[i].length == 2
1 <= width_i, height_i <= 10⁵

Solution: Hashtable

Use aspect ratio as the key.

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

C++

// Author: Huahua

class Solution {

public:

long long interchangeableRectangles(vector<vector<int>>& rectangles) {

long long ans = 0;

unordered_map<long long, int> m;

for (const auto& r : rectangles) {

long long d = gcd(r[0], r[1]);

ans += m[((r[0] / d) << 20) | (r[1] / d)]++;

}

return ans;

}

};

花花酱 LeetCode 2000. Reverse Prefix of Word

By zxi on November 20, 2021

Given a 0-indexed string word and a character ch, reverse the segment of word that starts at index 0 and ends at the index of the first occurrence of ch (inclusive). If the character ch does not exist in word, do nothing.

For example, if word = "abcdefd" and ch = "d", then you should reverse the segment that starts at 0 and ends at 3 (inclusive). The resulting string will be "dcbaefd".

Return the resulting string.

Example 1:

Input: word = "abcdefd", ch = "d"
Output: "dcbaefd"
Explanation: The first occurrence of "d" is at index 3. 
Reverse the part of word from 0 to 3 (inclusive), the resulting string is "dcbaefd".

Example 2:

Input: word = "xyxzxe", ch = "z"
Output: "zxyxxe"
Explanation: The first and only occurrence of "z" is at index 3.
Reverse the part of word from 0 to 3 (inclusive), the resulting string is "zxyxxe".

Example 3:

Input: word = "abcd", ch = "z"
Output: "abcd"
Explanation: "z" does not exist in word.
You should not do any reverse operation, the resulting string is "abcd".

Constraints:

1 <= word.length <= 250
word consists of lowercase English letters.
ch is a lowercase English letter.

Solution: Brute Force

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

C++

// Author: Huahua

class Solution {

public:

string reversePrefix(string word, char ch) {

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

if (word[i] == ch) return

string(rbegin(word) + word.size() - i - 1, rend(word)) + word.substr(i + 1);

return word;

}

};

Huahua's Tech Road

花花酱 LeetCode 2078. Two Furthest Houses With Different Colors

Solution 1: Brute Force

C++

Solution 2: Greedy / One pass

C++

花花酱 LeetCode 2003. Smallest Missing Genetic Value in Each Subtree

Solution: DFS on a single path

C++

花花酱 LeetCode 2002. Maximum Product of the Length of Two Palindromic Subsequences

Solution 1: DFS

C++

Solution: Subsets + Bitmask + All Pairs

C++

花花酱 LeetCode 2001. Number of Pairs of Interchangeable Rectangles

Solution: Hashtable

C++

花花酱 LeetCode 2000. Reverse Prefix of Word

Solution: Brute Force

C++