Huahua’s Tech Road

花花酱 LeetCode 2068. Check Whether Two Strings are Almost Equivalent

By zxi on November 13, 2021

Two strings word1 and word2 are considered almost equivalent if the differences between the frequencies of each letter from 'a' to 'z' between word1 and word2 is at most 3.

Given two strings word1 and word2, each of length n, return true if word1 and word2 are almost equivalent, or false otherwise.

The frequency of a letter x is the number of times it occurs in the string.

Example 1:

Input: word1 = "aaaa", word2 = "bccb"
Output: false
Explanation: There are 4 'a's in "aaaa" but 0 'a's in "bccb".
The difference is 4, which is more than the allowed 3.

Example 2:

Input: word1 = "abcdeef", word2 = "abaaacc"
Output: true
Explanation: The differences between the frequencies of each letter in word1 and word2 are at most 3:
- 'a' appears 1 time in word1 and 4 times in word2. The difference is 3.
- 'b' appears 1 time in word1 and 1 time in word2. The difference is 0.
- 'c' appears 1 time in word1 and 2 times in word2. The difference is 1.
- 'd' appears 1 time in word1 and 0 times in word2. The difference is 1.
- 'e' appears 2 times in word1 and 0 times in word2. The difference is 2.
- 'f' appears 1 time in word1 and 0 times in word2. The difference is 1.

Example 3:

Input: word1 = "cccddabba", word2 = "babababab"
Output: true
Explanation: The differences between the frequencies of each letter in word1 and word2 are at most 3:
- 'a' appears 2 times in word1 and 4 times in word2. The difference is 2.
- 'b' appears 2 times in word1 and 5 times in word2. The difference is 3.
- 'c' appears 3 times in word1 and 0 times in word2. The difference is 3.
- 'd' appears 2 times in word1 and 0 times in word2. The difference is 2.

Constraints:

n == word1.length == word2.length
1 <= n <= 100
word1 and word2 consist only of lowercase English letters.

Solution: Hashtable

Use a hashtable to track the relative frequency of a letter.

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

C++

// Author: Huahua

class Solution {

public:

bool checkAlmostEquivalent(string word1, string word2) {

vector<int> m(26);

for (char c: word1) ++m[c - 'a'];

for (char c: word2) --m[c - 'a'];

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

if (abs(m[i]) > 3) return false;

return true;

}

};

花花酱 LeetCode 2065. Maximum Path Quality of a Graph

By zxi on November 7, 2021

There is an undirected graph with n nodes numbered from 0 to n - 1 (inclusive). You are given a 0-indexed integer array values where values[i] is the value of the i^th node. You are also given a 0-indexed 2D integer array edges, where each edges[j] = [u_j, v_j, time_j] indicates that there is an undirected edge between the nodes u_j and v_j,and it takes time_j seconds to travel between the two nodes. Finally, you are given an integer maxTime.

A valid path in the graph is any path that starts at node 0, ends at node 0, and takes at most maxTime seconds to complete. You may visit the same node multiple times. The quality of a valid path is the sum of the values of the unique nodes visited in the path (each node’s value is added at most once to the sum).

Return the maximum quality of a valid path.

Note: There are at most four edges connected to each node.

Example 1:

Input: values = [0,32,10,43], edges = [[0,1,10],[1,2,15],[0,3,10]], maxTime = 49
Output: 75
Explanation:
One possible path is 0 -> 1 -> 0 -> 3 -> 0. The total time taken is 10 + 10 + 10 + 10 = 40 <= 49.
The nodes visited are 0, 1, and 3, giving a maximal path quality of 0 + 32 + 43 = 75.

Example 2:

Input: values = [5,10,15,20], edges = [[0,1,10],[1,2,10],[0,3,10]], maxTime = 30
Output: 25
Explanation:
One possible path is 0 -> 3 -> 0. The total time taken is 10 + 10 = 20 <= 30.
The nodes visited are 0 and 3, giving a maximal path quality of 5 + 20 = 25.

Example 3:

Input: values = [1,2,3,4], edges = [[0,1,10],[1,2,11],[2,3,12],[1,3,13]], maxTime = 50
Output: 7
Explanation:
One possible path is 0 -> 1 -> 3 -> 1 -> 0. The total time taken is 10 + 13 + 13 + 10 = 46 <= 50.
The nodes visited are 0, 1, and 3, giving a maximal path quality of 1 + 2 + 4 = 7.

Example 4:

Input: values = [0,1,2], edges = [[1,2,10]], maxTime = 10
Output: 0
Explanation: 
The only path is 0. The total time taken is 0.
The only node visited is 0, giving a maximal path quality of 0.

Constraints:

n == values.length
1 <= n <= 1000
0 <= values[i] <= 10⁸
0 <= edges.length <= 2000
edges[j].length == 3
0 <= u_j< v_j <= n - 1
10 <= time_j, maxTime <= 100
All the pairs [u_j, v_j] are unique.
There are at most four edges connected to each node.
The graph may not be connected.

Solution: DFS

Given time >= 10 and maxTime <= 100, the path length is at most 10, given at most four edges connected to each node.
Time complexity: O(4¹⁰)
Space complexity: O(n)

C++

// Author: Huahua

class Solution {

public:

int maximalPathQuality(vector<int>& values, vector<vector<int>>& edges, int maxTime) {

const int n = values.size();

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

for (const auto& e : edges) {

g[e[0]].emplace_back(e[1], e[2]);

g[e[1]].emplace_back(e[0], e[2]);

}

vector<int> seen(n);

int ans = 0;

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

if (++seen[u] == 1) s += values[u];

if (u == 0) ans = max(ans, s);

for (auto [v, d] : g[u])

if (t + d <= maxTime) dfs(v, t + d, s);

if (--seen[u] == 0) s -= values[u];

};

dfs(0, 0, 0);

return ans;

}

};

花花酱 LeetCode 2064. Minimized Maximum of Products Distributed to Any Store

By zxi on November 7, 2021

You are given an integer n indicating there are n specialty retail stores. There are m product types of varying amounts, which are given as a 0-indexed integer array quantities, where quantities[i] represents the number of products of the i^th product type.

You need to distribute all products to the retail stores following these rules:

A store can only be given at most one product type but can be given any amount of it.
After distribution, each store will be given some number of products (possibly 0). Let x represent the maximum number of products given to any store. You want x to be as small as possible, i.e., you want to minimize the maximum number of products that are given to any store.

Return the minimum possible x.

Example 1:

Input: n = 6, quantities = [11,6]
Output: 3
Explanation: One optimal way is:
- The 11 products of type 0 are distributed to the first four stores in these amounts: 2, 3, 3, 3
- The 6 products of type 1 are distributed to the other two stores in these amounts: 3, 3
The maximum number of products given to any store is max(2, 3, 3, 3, 3, 3) = 3.

Example 2:

Input: n = 7, quantities = [15,10,10]
Output: 5
Explanation: One optimal way is:
- The 15 products of type 0 are distributed to the first three stores in these amounts: 5, 5, 5
- The 10 products of type 1 are distributed to the next two stores in these amounts: 5, 5
- The 10 products of type 2 are distributed to the last two stores in these amounts: 5, 5
The maximum number of products given to any store is max(5, 5, 5, 5, 5, 5, 5) = 5.

Example 3:

Input: n = 1, quantities = [100000]
Output: 100000
Explanation: The only optimal way is:
- The 100000 products of type 0 are distributed to the only store.
The maximum number of products given to any store is max(100000) = 100000.

Constraints:

m == quantities.length
1 <= m <= n <= 10⁵
1 <= quantities[i] <= 10⁵

Solution: Binary Search

Find the smallest max product s.t. all products can be distribute to <= n stores.

Time complexity: O(nlog(max(q)))
Space complexity: O(1)

C++

// Author: Huahua

class Solution {

public:

int minimizedMaximum(int n, vector<int>& quantities) {

int l = 1;

int r = *max_element(begin(quantities), end(quantities)) + 1;

while (l < r) {

int cur = 0;

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

for (int q : quantities)

cur += (q + (m - 1)) / m;

if (cur <= n)

r = m;

else

l = m + 1;

}

return l;

}

};

花花酱 LeetCode 2063. Vowels of All Substrings

By zxi on November 7, 2021

Given a string word, return the sum of the number of vowels ('a', 'e', 'i', 'o', and 'u') in every substring of word.

A substring is a contiguous (non-empty) sequence of characters within a string.

Note: Due to the large constraints, the answer may not fit in a signed 32-bit integer. Please be careful during the calculations.

Example 1:

Input: word = "aba"
Output: 6
Explanation: 
All possible substrings are: "a", "ab", "aba", "b", "ba", and "a".
- "b" has 0 vowels in it
- "a", "ab", "ba", and "a" have 1 vowel each
- "aba" has 2 vowels in it
Hence, the total sum of vowels = 0 + 1 + 1 + 1 + 1 + 2 = 6.

Example 2:

Input: word = "abc"
Output: 3
Explanation: 
All possible substrings are: "a", "ab", "abc", "b", "bc", and "c".
- "a", "ab", and "abc" have 1 vowel each
- "b", "bc", and "c" have 0 vowels each
Hence, the total sum of vowels = 1 + 1 + 1 + 0 + 0 + 0 = 3.

Example 3:

Input: word = "ltcd"
Output: 0
Explanation: There are no vowels in any substring of "ltcd".

Example 4:

Input: word = "noosabasboosa"
Output: 237
Explanation: There are a total of 237 vowels in all the substrings.

Constraints:

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

Solution: Math

For a vowel at index i,
we can choose 0, 1, … i as starting point
choose i, i+1, …, n -1 as end point.
There will be (i – 0 + 1) * (n – 1 – i + 1) possible substrings that contains word[i].

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

C++

class Solution {

public:

long long countVowels(string word) {

const long long n = word.size();

long long ans = 0;

for (long long i = 0; i < n; ++i) {

switch (word[i]) {

case 'a':

case 'e':

case 'i':

case 'o':

case 'u':

ans += (i + 1) * (n - 1 - i + 1);

break;

}

return ans;

}

};

花花酱 LeetCode 2062. Count Vowel Substrings of a String

By zxi on November 7, 2021

A substring is a contiguous (non-empty) sequence of characters within a string.

A vowel substring is a substring that only consists of vowels ('a', 'e', 'i', 'o', and 'u') and has all five vowels present in it.

Given a string word, return the number of vowel substrings in word.

Example 1:

Input: word = "aeiouu"
Output: 2
Explanation: The vowel substrings of word are as follows (underlined):
- "aeiouu"
- "aeiouu"

Example 2:

Input: word = "unicornarihan"
Output: 0
Explanation: Not all 5 vowels are present, so there are no vowel substrings.

Example 3:

Input: word = "cuaieuouac"
Output: 7
Explanation: The vowel substrings of word are as follows (underlined):
- "cuaieuouac"
- "cuaieuouac"
- "cuaieuouac"
- "cuaieuouac"
- "cuaieuouac"
- "cuaieuouac"
- "cuaieuouac"

Example 4:

Input: word = "bbaeixoubb"
Output: 0
Explanation: The only substrings that contain all five vowels also contain consonants, so there are no vowel substrings.

Constraints:

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

Solution 1: Brute Force

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

C++

// Author: Huahua

class Solution {

public:

int countVowelSubstrings(string_view word) {

const int n = word.size();

auto check = [&](string_view s) {

set<int> seen;

string vowels {"aeiou"};

for (char c : s) {

if (vowels.find(c) == string::npos) return false;

seen.insert(c);

}

return seen.size() == 5;

};

int ans = 0;

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

for (int l = 5; i + l <= n; ++l)

if (check(word.substr(i, l))) ++ans;

return ans;

}

};

Solution 2: Sliding Window / Three Pointers

Maintain a window [i, j] that contain all 5 vowels, find k s.t. [k + 1, i] no longer container 5 vowels.
# of valid substrings end with j will be (k – i).

##aeiouaeioo##
..i....k...j..
i = 3, k = 8, j = 12

Valid substrings are:
aeiouaeioo .eiouaeioo ..iouaeioo ...ouaeioo ....uaeioo
8 – 3 = 5

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

C++

// Author: Huahua

class Solution {

public:

int countVowelSubstrings(string_view word) {

constexpr string_view vowels{"aeiou"};

int ans = 0;

unordered_map<char, int> m;

for (char c : vowels) m[c] = 0;

for (size_t i = 0, j = 0, k = 0, v = 0; j < word.size(); ++j) {

if (m.count(word[j])) {

v += (++m[word[j]] == 1);

while (v == 5)

v -= (--m[word[k++]] == 0);

ans += k - i;

} else {

for (char c : vowels) m[c] = 0;

v = 0;

i = k = j + 1;

}

return ans;

}

};

Huahua's Tech Road

花花酱 LeetCode 2068. Check Whether Two Strings are Almost Equivalent

Solution: Hashtable

C++

花花酱 LeetCode 2065. Maximum Path Quality of a Graph

Solution: DFS

C++

花花酱 LeetCode 2064. Minimized Maximum of Products Distributed to Any Store

Solution: Binary Search

C++

花花酱 LeetCode 2063. Vowels of All Substrings

Solution: Math

C++

花花酱 LeetCode 2062. Count Vowel Substrings of a String

C++

Solution 2: Sliding Window / Three Pointers

C++