Huahua’s Tech Road

花花酱 LeetCode 2054. Two Best Non-Overlapping Events

By zxi on November 1, 2021

You are given a 0-indexed 2D integer array of events where events[i] = [startTime_i, endTime_i, value_i]. The i^th event starts at startTime_iand ends at endTime_i, and if you attend this event, you will receive a value of value_i. You can choose at most two non-overlapping events to attend such that the sum of their values is maximized.

Return this maximum sum.

Note that the start time and end time is inclusive: that is, you cannot attend two events where one of them starts and the other ends at the same time. More specifically, if you attend an event with end time t, the next event must start at or after t + 1.

Example 1:

Input: events = [[1,3,2],[4,5,2],[2,4,3]]
Output: 4
Explanation: Choose the green events, 0 and 1 for a sum of 2 + 2 = 4.

Example 2:

Input: events = [[1,3,2],[4,5,2],[1,5,5]]
Output: 5
Explanation: Choose event 2 for a sum of 5.

Example 3:

Input: events = [[1,5,3],[1,5,1],[6,6,5]]
Output: 8
Explanation: Choose events 0 and 2 for a sum of 3 + 5 = 8.

Constraints:

2 <= events.length <= 10⁵
events[i].length == 3
1 <= startTime_i <= endTime_i <= 10⁹
1 <= value_i <= 10⁶

Solution: Sort + Heap

Sort events by start time, process them from left to right.

Use a min heap to store the events processed so far, a variable cur to track the max value of a non-overlapping event.

For a given event, pop all non-overlapping events whose end time is smaller than its start time and update cur.

ans = max(val + cur)

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

C++

// Author: Huahua

class Solution {

public:

int maxTwoEvents(vector<vector<int>>& events) {

using E = pair<int,int>;

sort(begin(events), end(events));

priority_queue<E, vector<E>, greater<E>> q; // (end_time, val)

int ans = 0;

int cur = 0;

for (const auto& e : events) {

while (!q.empty() && q.top().first < e[0]) {

cur = max(cur, q.top().second);

q.pop();

}

ans = max(ans, cur + e[2]);

q.emplace(e[1], e[2]);

}

return ans;

}

};

花花酱 LeetCode 2053. Kth Distinct String in an Array

By zxi on November 1, 2021

A distinct string is a string that is present only once in an array.

Given an array of strings arr, and an integer k, return the k^th distinct string present in arr. If there are fewer than k distinct strings, return an empty string "".

Note that the strings are considered in the order in which they appear in the array.

Example 1:

Input: arr = ["d","b","c","b","c","a"], k = 2
Output: "a"
Explanation:
The only distinct strings in arr are "d" and "a".
"d" appears 1^st, so it is the 1^st distinct string.
"a" appears 2^nd, so it is the 2^nd distinct string.
Since k == 2, "a" is returned.

Example 2:

Input: arr = ["aaa","aa","a"], k = 1
Output: "aaa"
Explanation:
All strings in arr are distinct, so the 1^st string "aaa" is returned.

Example 3:

Input: arr = ["a","b","a"], k = 3
Output: ""
Explanation:
The only distinct string is "b". Since there are fewer than 3 distinct strings, we return an empty string "".

Constraints:

1 <= k <= arr.length <= 1000
1 <= arr[i].length <= 5
arr[i] consists of lowercase English letters.

Solution: Hashtable

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

C++

// Author: Huahua

class Solution {

public:

string kthDistinct(vector<string>& arr, int k) {

unordered_map<string, int> m;

for (const string& s : arr)

++m[s];

for (const string& s : arr)

if (m[s] == 1 && --k == 0) return s;

return "";

}

};

花花酱 LeetCode 2049. Count Nodes With the Highest Score

By zxi on October 26, 2021

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

Each node has a score. To find the score of a node, consider if the node and the edges connected to it were removed. The tree would become one or more non-empty subtrees. The size of a subtree is the number of the nodes in it. The score of the node is the product of the sizes of all those subtrees.

Return the number of nodes that have the highest score.

Example 1:

Input: parents = [-1,2,0,2,0]
Output: 3
Explanation:
- The score of node 0 is: 3 * 1 = 3
- The score of node 1 is: 4 = 4
- The score of node 2 is: 1 * 1 * 2 = 2
- The score of node 3 is: 4 = 4
- The score of node 4 is: 4 = 4
The highest score is 4, and three nodes (node 1, node 3, and node 4) have the highest score.

Example 2:

Input: parents = [-1,2,0]
Output: 2
Explanation:
- The score of node 0 is: 2 = 2
- The score of node 1 is: 2 = 2
- The score of node 2 is: 1 * 1 = 1
The highest score is 2, and two nodes (node 0 and node 1) have the highest score.

Constraints:

n == parents.length
2 <= n <= 10⁵
parents[0] == -1
0 <= parents[i] <= n - 1 for i != 0
parents represents a valid binary tree.

Solution: Recursion

Write a function that returns the element of a subtree rooted at node.

We can compute the score based on:
1. size of the subtree(s)
2. # of children

Root is a special case whose score is max(c[0], 1) * max(c[1], 1).

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

C++

// Author: Huahua

class Solution {

public:

int countHighestScoreNodes(vector<int>& parents) {

const int n = parents.size();

long high = 0;

int ans = 0;

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

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

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

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

long c[2] = {0, 0};

for (int i = 0; i < tree[node].size(); ++i)

c[i] = dfs(tree[node][i]);

long score = 0;

if (node == 0) // case #1: root

score = max(c[0], 1l) * max(c[1], 1l);

else if (tree[node].size() == 0) // case #2: leaf

score = n - 1;

else if (tree[node].size() == 1) // case #3: one child

score = c[0] * (n - c[0] - 1);

else // case #4: two children

score = c[0] * c[1] * (n - c[0] - c[1] - 1);

if (score > high) {

high = score;

ans = 1;

} else if (score == high) {

++ans;

}

return 1 + c[0] + c[1];

};

dfs(0);

return ans;

}

};

花花酱 LeetCode 2048. Next Greater Numerically Balanced Number

By zxi on October 25, 2021

An integer x is numerically balanced if for every digit d in the number x, there are exactly d occurrences of that digit in x.

Given an integer n, return the smallest numerically balanced number strictly greater than n.

Example 1:

Input: n = 1
Output: 22
Explanation: 
22 is numerically balanced since:
- The digit 2 occurs 2 times. 
It is also the smallest numerically balanced number strictly greater than 1.

Example 2:

Input: n = 1000
Output: 1333
Explanation: 
1333 is numerically balanced since:
- The digit 1 occurs 1 time.
- The digit 3 occurs 3 times. 
It is also the smallest numerically balanced number strictly greater than 1000.
Note that 1022 cannot be the answer because 0 appeared more than 0 times.

Example 3:

Input: n = 3000
Output: 3133
Explanation: 
3133 is numerically balanced since:
- The digit 1 occurs 1 time.
- The digit 3 occurs 3 times.
It is also the smallest numerically balanced number strictly greater than 3000.

Constraints:

0 <= n <= 10⁶

Solution: Permutation

Time complexity: O(log(n)!)
Space complexity: O(log(n)) ?

C++

// Author: Huahua

class Solution {

public:

int nextBeautifulNumber(int n) {

const string t = to_string(n);

vector<int> nums{1,

22,

122, 333,

1333, 4444,

14444, 22333, 55555,

122333, 155555, 224444, 666666};

int ans = 1224444;

for (int num : nums) {

string s = to_string(num);

if (s.size() < t.size()) continue;

else if (s.size() > t.size()) {

ans = min(ans, num);

} else { // same length

do {

if (s > t) ans = min(ans, stoi(s));

} while (next_permutation(begin(s), end(s)));

}

return ans;

}

};

花花酱 LeetCode 2047. Number of Valid Words in a Sentence

By zxi on October 24, 2021

A sentence consists of lowercase letters ('a' to 'z'), digits ('0' to '9'), hyphens ('-'), punctuation marks ('!', '.', and ','), and spaces (' ') only. Each sentence can be broken down into one or more tokens separated by one or more spaces ' '.

A token is a valid word if:

It only contains lowercase letters, hyphens, and/or punctuation (no digits).
There is at most one hyphen '-'. If present, it should be surrounded by lowercase characters ("a-b" is valid, but "-ab" and "ab-" are not valid).
There is at most one punctuation mark. If present, it should be at the end of the token.

Examples of valid words include "a-b.", "afad", "ba-c", "a!", and "!".

Given a string sentence, return the number of valid words in sentence.

Example 1:

Input: sentence = "cat and  dog"
Output: 3
Explanation: The valid words in the sentence are "cat", "and", and "dog".

Example 2:

Input: sentence = "!this  1-s b8d!"
Output: 0
Explanation: There are no valid words in the sentence.
"!this" is invalid because it starts with a punctuation mark.
"1-s" and "b8d" are invalid because they contain digits.

Example 3:

Input: sentence = "alice and  bob are playing stone-game10"
Output: 5
Explanation: The valid words in the sentence are "alice", "and", "bob", "are", and "playing".
"stone-game10" is invalid because it contains digits.

Example 4:

Input: sentence = "he bought 2 pencils, 3 erasers, and 1  pencil-sharpener."
Output: 6
Explanation: The valid words in the sentence are "he", "bought", "pencils,", "erasers,", "and", and "pencil-sharpener.".

Constraints:

1 <= sentence.length <= 1000
sentence only contains lowercase English letters, digits, ' ', '-', '!', '.', and ','.
There will be at least 1 token.

Solution 1: Brute Force

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

C++

// Author: Huahua

class Solution {

public:

int countValidWords(string sentence) {

stringstream ss(sentence);

string word;

int ans = 0;

while (ss >> word) {

bool valid = true;

int hyphen = 0;

int punctuation = 0;

char p = ' ';

for (char c : word) {

if (c == '-') {

if (++hyphen > 1 || !isalpha(p)) {

valid = false;

break;

}

} else if (c == '!' || c == '.' || c == ',') {

if (++punctuation > 1 || p == '-') {

valid = false;

break;

}

} else if (isalpha(c)) {

if (punctuation) {

valid = false;

break;

}

} else {

valid = false;

break;

}

p = c;

}

if (word.back() == '-')

valid = false;

if (valid) ++ans;

}

return ans;

}

};

Solution 2: Regex

Time complexity: O(n^2)?
Space complexity: O(1)

Python

# Author: Huahua

class Solution:

def countValidWords(self, sentence: str) -> int:

ans = 0

for word in sentence.split():

if word.strip() and re.fullmatch('^([a-z]+(-?[a-z]+)?)?[\.,!]?$', word.strip()):

ans += 1

return ans

Huahua's Tech Road

花花酱 LeetCode 2054. Two Best Non-Overlapping Events

Solution: Sort + Heap

C++

花花酱 LeetCode 2053. Kth Distinct String in an Array

Solution: Hashtable

C++

花花酱 LeetCode 2049. Count Nodes With the Highest Score

Solution: Recursion

C++

花花酱 LeetCode 2048. Next Greater Numerically Balanced Number

Solution: Permutation

C++

花花酱 LeetCode 2047. Number of Valid Words in a Sentence

Solution 1: Brute Force

C++

Solution 2: Regex

Python