Huahua’s Tech Road

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

}

};

花花酱 LeetCode 2050. Parallel Courses III

By zxi on November 18, 2021

You are given an integer n, which indicates that there are n courses labeled from 1 to n. You are also given a 2D integer array relations where relations[j] = [prevCourse_j, nextCourse_j] denotes that course prevCourse_j has to be completed before course nextCourse_j (prerequisite relationship). Furthermore, you are given a 0-indexed integer array time where time[i] denotes how many months it takes to complete the (i+1)^th course.

You must find the minimum number of months needed to complete all the courses following these rules:

You may start taking a course at any time if the prerequisites are met.
Any number of courses can be taken at the same time.

Return the minimum number of months needed to complete all the courses.

Note: The test cases are generated such that it is possible to complete every course (i.e., the graph is a directed acyclic graph).

Example 1:

Input: n = 3, relations = [[1,3],[2,3]], time = [3,2,5]
Output: 8
Explanation: The figure above represents the given graph and the time required to complete each course. 
We start course 1 and course 2 simultaneously at month 0.
Course 1 takes 3 months and course 2 takes 2 months to complete respectively.
Thus, the earliest time we can start course 3 is at month 3, and the total time required is 3 + 5 = 8 months.

Example 2:

Input: n = 5, relations = [[1,5],[2,5],[3,5],[3,4],[4,5]], time = [1,2,3,4,5]
Output: 12
Explanation: The figure above represents the given graph and the time required to complete each course.
You can start courses 1, 2, and 3 at month 0.
You can complete them after 1, 2, and 3 months respectively.
Course 4 can be taken only after course 3 is completed, i.e., after 3 months. It is completed after 3 + 4 = 7 months.
Course 5 can be taken only after courses 1, 2, 3, and 4 have been completed, i.e., after max(1,2,3,7) = 7 months.
Thus, the minimum time needed to complete all the courses is 7 + 5 = 12 months.

Constraints:

1 <= n <= 5 * 10⁴
0 <= relations.length <= min(n * (n - 1) / 2, 5 * 10⁴)
relations[j].length == 2
1 <= prevCourse_j, nextCourse_j <= n
prevCourse_j != nextCourse_j
All the pairs [prevCourse_j, nextCourse_j] are unique.
time.length == n
1 <= time[i] <= 10⁴
The given graph is a directed acyclic graph.

Solution: Topological Sorting

Time complexity: O(V+E)
Space complexity: O(V+E)

C++

// Author: Huahua

class Solution {

public:

int minimumTime(int n, vector<vector<int>>& relations, vector<int>& time) {

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

for (const auto& r: relations)

g[r[0] - 1].push_back(r[1] - 1);

vector<int> t(n, -1);

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

if (t[u] != -1) return t[u];

t[u] = 0;

for (int v : g[u])

t[u] = max(t[u], dfs(v));

return t[u] += time[u];

};

int ans = 0;

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

ans = max(ans, dfs(i));

return ans;

}

};

Python3

class Solution:

def minimumTime(self, n: int, relations: List[List[int]], time: List[int]) -> int:

g = [[] for _ in range(n)]

for u, v in relations: g[u - 1].append(v - 1)

@cache

def dfs(u: int) -> int:

return max([dfs(v) for v in g[u]] + [0]) + time[u]

return max(dfs(u) for u in range(n))

花花酱 LeetCode 2076. Process Restricted Friend Requests

By zxi on November 15, 2021

You are given an integer n indicating the number of people in a network. Each person is labeled from 0 to n - 1.

You are also given a 0-indexed 2D integer array restrictions, where restrictions[i] = [x_i, y_i] means that person x_i and person y_i cannot become friends,either directly or indirectly through other people.

Initially, no one is friends with each other. You are given a list of friend requests as a 0-indexed 2D integer array requests, where requests[j] = [u_j, v_j] is a friend request between person u_j and person v_j.

A friend request is successful if u_j and v_j can be friends. Each friend request is processed in the given order (i.e., requests[j] occurs before requests[j + 1]), and upon a successful request, u_j and v_j become direct friends for all future friend requests.

Return a boolean array result, where each result[j] is true if the j^th friend request is successful or false if it is not.

Note: If u_j and v_j are already direct friends, the request is still successful.

Example 1:

Input: n = 3, restrictions = [[0,1]], requests = [[0,2],[2,1]]
Output: [true,false]
Explanation:
Request 0: Person 0 and person 2 can be friends, so they become direct friends. 
Request 1: Person 2 and person 1 cannot be friends since person 0 and person 1 would be indirect friends (1--2--0).

Example 2:

Input: n = 3, restrictions = [[0,1]], requests = [[1,2],[0,2]]
Output: [true,false]
Explanation:
Request 0: Person 1 and person 2 can be friends, so they become direct friends.
Request 1: Person 0 and person 2 cannot be friends since person 0 and person 1 would be indirect friends (0--2--1).

Example 3:

Input: n = 5, restrictions = [[0,1],[1,2],[2,3]], requests = [[0,4],[1,2],[3,1],[3,4]]
Output: [true,false,true,false]
Explanation:
Request 0: Person 0 and person 4 can be friends, so they become direct friends.
Request 1: Person 1 and person 2 cannot be friends since they are directly restricted.
Request 2: Person 3 and person 1 can be friends, so they become direct friends.
Request 3: Person 3 and person 4 cannot be friends since person 0 and person 1 would be indirect friends (0--4--3--1).

Constraints:

2 <= n <= 1000
0 <= restrictions.length <= 1000
restrictions[i].length == 2
0 <= x_i, y_i <= n - 1
x_i != y_i
1 <= requests.length <= 1000
requests[j].length == 2
0 <= u_j, v_j <= n - 1
u_j != v_j

Solution: Union Find / Brute Force

For each request, check all restrictions.

Time complexity: O(req * res)
Space complexity: O(n)

C++

// Author: Huahua

class Solution {

public:

vector<bool> friendRequests(int n, vector<vector<int>>& restrictions, vector<vector<int>>& requests) {

vector<int> parents(n);

iota(begin(parents), end(parents), 0);

function<int(int)> find = [&](int x) {

if (parents[x] == x) return x;

return parents[x] = find(parents[x]);

};

auto check = [&](int u, int v) {

for (const auto& r : restrictions) {

int pu = find(r[0]);

int pv = find(r[1]);

if ((pu == u && pv == v) || (pu == v && pv == u))

return false;

}

return true;

};

vector<bool> ans;

for (const auto& r : requests) {

int pu = find(r[0]);

int pv = find(r[1]);

if (pu == pv || check(pu, pv)) {

parents[pu] = pv;

ans.push_back(true);

} else {

ans.push_back(false);

}

return ans;

}

};

Huahua's Tech Road

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

花花酱 LeetCode 2050. Parallel Courses III

Solution: Topological Sorting

C++

Python3

花花酱 LeetCode 2076. Process Restricted Friend Requests

C++