Huahua’s Tech Road

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

}

};

花花酱 LeetCode 2059. Minimum Operations to Convert Number

By zxi on November 4, 2021

You are given a 0-indexed integer array nums containing distinct numbers, an integer start, and an integer goal. There is an integer x that is initially set to start, and you want to perform operations on x such that it is converted to goal. You can perform the following operation repeatedly on the number x:

If 0 <= x <= 1000, then for any index i in the array (0 <= i < nums.length), you can set x to any of the following:

x + nums[i]
x - nums[i]
x ^ nums[i] (bitwise-XOR)

Note that you can use each nums[i] any number of times in any order. Operations that set x to be out of the range 0 <= x <= 1000 are valid, but no more operations can be done afterward.

Return the minimum number of operations needed to convert x = start into goal, and -1 if it is not possible.

Example 1:

Input: nums = [1,3], start = 6, goal = 4
Output: 2
Explanation:
We can go from 6 → 7 → 4 with the following 2 operations.
- 6 ^ 1 = 7
- 7 ^ 3 = 4

Example 2:

Input: nums = [2,4,12], start = 2, goal = 12
Output: 2
Explanation:
We can go from 2 → 14 → 12 with the following 2 operations.
- 2 + 12 = 14
- 14 - 2 = 12

Example 3:

Input: nums = [3,5,7], start = 0, goal = -4
Output: 2
Explanation:
We can go from 0 → 3 → -4 with the following 2 operations. 
- 0 + 3 = 3
- 3 - 7 = -4
Note that the last operation sets x out of the range 0 <= x <= 1000, which is valid.

Example 4:

Input: nums = [2,8,16], start = 0, goal = 1
Output: -1
Explanation:
There is no way to convert 0 into 1.

Example 5:

Input: nums = [1], start = 0, goal = 3

Output: 3

Explanation:

We can go from 0 → 1 → 2 → 3 with the following 3 operations.

- 0 + 1 = 1

- 1 + 1 = 2

- 2 + 1 = 3

Constraints:

1 <= nums.length <= 1000
-10⁹ <= nums[i], goal <= 10⁹
0 <= start <= 1000
start != goal
All the integers in nums are distinct.

Solution: BFS

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

C++

// Author: Huahua

class Solution {

public:

int minimumOperations(vector<int>& nums, int start, int goal) {

vector<int> seen(1001);

queue<int> q{{start}};

for (int ans = 1, s = 1; !q.empty(); ++ans, s = q.size()) {

while (s--) {

int x = q.front(); q.pop();

for (int n : nums)

for (int t : {x + n, x - n, x ^ n})

if (t == goal)

return ans;

else if (t < 0 || t > 1000 || seen[t]++)

continue;

else

q.push(t);

}

return -1;

}

};

LeetCode 2058. Find the Minimum and Maximum Number of Nodes Between Critical Points

By zxi on November 3, 2021

A critical point in a linked list is defined as either a local maxima or a local minima.

A node is a local maxima if the current node has a value strictly greater than the previous node and the next node.

A node is a local minima if the current node has a value strictly smaller than the previous node and the next node.

Note that a node can only be a local maxima/minima if there exists both a previous node and a next node.

Given a linked list head, return an array of length 2 containing [minDistance, maxDistance] where minDistance is the minimum distance between any two distinct critical points and maxDistance is the maximum distance between any two distinct critical points. If there are fewer than two critical points, return [-1, -1].

Example 1:

Input: head = [3,1]
Output: [-1,-1]
Explanation: There are no critical points in [3,1].

Example 2:

Input: head = [5,3,1,2,5,1,2]
Output: [1,3]
Explanation: There are three critical points:
- [5,3,1,2,5,1,2]: The third node is a local minima because 1 is less than 3 and 2.
- [5,3,1,2,5,1,2]: The fifth node is a local maxima because 5 is greater than 2 and 1.
- [5,3,1,2,5,1,2]: The sixth node is a local minima because 1 is less than 5 and 2.
The minimum distance is between the fifth and the sixth node. minDistance = 6 - 5 = 1.
The maximum distance is between the third and the sixth node. maxDistance = 6 - 3 = 3.

Example 3:

Input: head = [1,3,2,2,3,2,2,2,7]
Output: [3,3]
Explanation: There are two critical points:
- [1,3,2,2,3,2,2,2,7]: The second node is a local maxima because 3 is greater than 1 and 2.
- [1,3,2,2,3,2,2,2,7]: The fifth node is a local maxima because 3 is greater than 2 and 2.
Both the minimum and maximum distances are between the second and the fifth node.
Thus, minDistance and maxDistance is 5 - 2 = 3.
Note that the last node is not considered a local maxima because it does not have a next node.

Example 4:

Input: head = [2,3,3,2]
Output: [-1,-1]
Explanation: There are no critical points in [2,3,3,2].

Constraints:

The number of nodes in the list is in the range [2, 10⁵].
1 <= Node.val <= 10⁵

Solution: One Pass

Track the first and last critical points.

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

C++

// Author: Huahua

class Solution {

public:

vector<int> nodesBetweenCriticalPoints(ListNode* head) {

ListNode* p = nullptr;

int min_dist = INT_MAX;

int max_dist = INT_MIN;

for (int i = 0, l = -1, r = -1; head; ++i, p = head, head = head->next) {

if (p && head->next) {

if ((head->val > p->val && head->val > head->next->val)

|| (head->val < p->val && head->val < head->next->val)) {

if (r != -1) {

min_dist = min(min_dist, i - r);

max_dist = max(max_dist, i - l);

} else {

l = i;

}

r = i;

}

return { min_dist == INT_MAX ? -1 : min_dist,

max_dist == INT_MIN ? -1 : max_dist };

}

};

花花酱 LeetCode 2057. Smallest Index With Equal Value

By zxi on November 3, 2021

Given a 0-indexed integer array nums, return the smallest index i of nums such that i mod 10 == nums[i], or -1 if such index does not exist.

x mod y denotes the remainder when x is divided by y.

Example 1:

Input: nums = [0,1,2]
Output: 0
Explanation: 
i=0: 0 mod 10 = 0 == nums[0].
i=1: 1 mod 10 = 1 == nums[1].
i=2: 2 mod 10 = 2 == nums[2].
All indices have i mod 10 == nums[i], so we return the smallest index 0.

Example 2:

Input: nums = [4,3,2,1]
Output: 2
Explanation: 
i=0: 0 mod 10 = 0 != nums[0].
i=1: 1 mod 10 = 1 != nums[1].
i=2: 2 mod 10 = 2 == nums[2].
i=3: 3 mod 10 = 3 != nums[3].
2 is the only index which has i mod 10 == nums[i].

Example 3:

Input: nums = [1,2,3,4,5,6,7,8,9,0]
Output: -1
Explanation: No index satisfies i mod 10 == nums[i].

Example 4:

Input: nums = [2,1,3,5,2]
Output: 1
Explanation: 1 is the only index with i mod 10 == nums[i].

Constraints:

1 <= nums.length <= 100
0 <= nums[i] <= 9

Solution: Brute Force

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

C++

// Author: Huahua

class Solution {

public:

int smallestEqual(vector<int>& nums) {

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

if (i % 10 == nums[i]) return i;

return -1;

}

};

花花酱 LeetCode 2055. Plates Between Candles

By zxi on November 3, 2021

There is a long table with a line of plates and candles arranged on top of it. You are given a 0-indexed string s consisting of characters '*' and '|' only, where a '*' represents a plate and a '|' represents a candle.

You are also given a 0-indexed 2D integer array queries where queries[i] = [left_i, right_i] denotes the substring s[left_i...right_i] (inclusive). For each query, you need to find the number of plates between candles that are in the substring. A plate is considered between candles if there is at least one candle to its left and at least one candle to its right in the substring.

For example, s = "||**||**|*", and a query [3, 8] denotes the substring "*||**|". The number of plates between candles in this substring is 2, as each of the two plates has at least one candle in the substring to its left and right.

Return an integer array answer where answer[i] is the answer to the i^th query.

Example 1:

Input: s = "**|**|***|", queries = [[2,5],[5,9]]
Output: [2,3]
Explanation:
- queries[0] has two plates between candles.
- queries[1] has three plates between candles.

Example 2:

Input: s = "***|**|*****|**||**|*", queries = [[1,17],[4,5],[14,17],[5,11],[15,16]]
Output: [9,0,0,0,0]
Explanation:
- queries[0] has nine plates between candles.
- The other queries have zero plates between candles.

Constraints:

3 <= s.length <= 10⁵
s consists of '*' and '|' characters.
1 <= queries.length <= 10⁵
queries[i].length == 2
0 <= left_i <= right_i < s.length

Solution: Binary Search

Store the indices of all candles into an array idx.

For each query q:
1. Find the left most candle whose index is greater or equal to left as l.
2. Find the left most candle whose index is greater than right, choose the previous candle as r.

[idx[l], idx[r]] is the range that are elements between two candles , there are (idx[r] – idx[l] + 1) elements in total and there are (r – l + 1) candles in the range. So the number of plates is (idx[r] – idx[l] + 1) – (r – l + 1) or (idx[r] – idx[l]) – (r – l)

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

C++

// Author: huahua

class Solution {

public:

vector<int> platesBetweenCandles(string s, vector<vector<int>>& queries) {

vector<int> idx;

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

if (s[i] == '|') idx.push_back(i);

vector<int> ans;

for (const auto& q : queries) {

const int l = lower_bound(begin(idx), end(idx), q[0]) - begin(idx);

const int r = upper_bound(begin(idx), end(idx), q[1]) - begin(idx) - 1;

ans.push_back(l >= r ? 0 : (idx[r] - idx[l]) - (r - l));

}

return ans;

}

};

Huahua's Tech Road

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

C++

Solution 2: Sliding Window / Three Pointers

C++

花花酱 LeetCode 2059. Minimum Operations to Convert Number

Solution: BFS

C++

LeetCode 2058. Find the Minimum and Maximum Number of Nodes Between Critical Points

Solution: One Pass

C++

花花酱 LeetCode 2057. Smallest Index With Equal Value

Solution: Brute Force

C++

花花酱 LeetCode 2055. Plates Between Candles

Solution: Binary Search

C++