# LeetCode Max Dot Product of Two Subsequences

1458. Max Dot Product of Two Subsequences

Given two arrays nums1 and nums2.

Return the maximum dot product between non-empty subsequences of nums1 and nums2 with the same length.

A subsequence of a array is a new array which is formed from the original array by deleting some (can be none) of the characters without disturbing the relative positions of the remaining characters. (ie, [2,3,5] is a subsequence of [1,2,3,4,5] while [1,5,3] is not).

Example 1:

Input: nums1 = [2,1,-2,5], nums2 = [3,0,-6]
Output: 18
Explanation: Take subsequence [2,-2] from nums1 and subsequence [3,-6] from nums2.
Their dot product is (2*3 + (-2)*(-6)) = 18.

Example 2:

Input: nums1 = [3,-2], nums2 = [2,-6,7]
Output: 21
Explanation: Take subsequence [3] from nums1 and subsequence [7] from nums2.
Their dot product is (3*7) = 21.

Example 3:

Input: nums1 = [-1,-1], nums2 = [1,1]
Output: -1
Explanation: Take subsequence [-1] from nums1 and subsequence [1] from nums2.
Their dot product is -1.

Constraints:

• 1 <= nums1.length, nums2.length <= 500
• -1000 <= nums1[i], nums2[i] <= 1000

• 不选nums1第i个数，dp[i][j]=dp[i-1][j]
• 不选nums2第j个数，dp[i][j]=dp[i][j-1]
• 既不选nums1第i个数，也不选nums2第j个数，dp[i][j]=dp[i-1][j-1]
• 既选nums1第i个数，也选nums2第j个数，dp[i][j]=dp[i-1][j-1]+nums1[i]*nums2[j]

class Solution {
public:
int maxDotProduct(vector<int>& nums1, vector<int>& nums2) {
int m = nums1.size(), n = nums2.size();
vector<vector<int>> dp(m + 1, vector<int>(n + 1, INT_MIN));
for (int i = 1; i <= m; ++i) {
for (int j = 1; j <= n; ++j) {
dp[i][j] = max(dp[i][j], dp[i - 1][j]);
dp[i][j] = max(dp[i][j], dp[i][j - 1]);
dp[i][j] = max(dp[i][j], dp[i - 1][j - 1]);
dp[i][j] = max(dp[i][j], max(dp[i - 1][j - 1], 0) + nums1[i - 1] * nums2[j - 1]);
}
}
return dp[m][n];
}
};

# LeetCode Pseudo-Palindromic Paths in a Binary Tree

5418. Pseudo-Palindromic Paths in a Binary Tree

Given a binary tree where node values are digits from 1 to 9. A path in the binary tree is said to be pseudo-palindromic if at least one permutation of the node values in the path is a palindrome.

Return the number of pseudo-palindromic paths going from the root node to leaf nodes.

Example 1:

Input: root = [2,3,1,3,1,null,1]
Output: 2
Explanation: The figure above represents the given binary tree. There are three paths going from the root node to leaf nodes: the red path [2,3,3], the green path [2,1,1], and the path [2,3,1]. Among these paths only red path and green path are pseudo-palindromic paths since the red path [2,3,3] can be rearranged in [3,2,3] (palindrome) and the green path [2,1,1] can be rearranged in [1,2,1] (palindrome).


Example 2:

Input: root = [2,1,1,1,3,null,null,null,null,null,1]
Output: 1
Explanation: The figure above represents the given binary tree. There are three paths going from the root node to leaf nodes: the green path [2,1,1], the path [2,1,3,1], and the path [2,1]. Among these paths only the green path is pseudo-palindromic since [2,1,1] can be rearranged in [1,2,1] (palindrome).


Example 3:

Input: root = [9]
Output: 1


Constraints:

• The given binary tree will have between 1 and 10^5 nodes.
• Node values are digits from 1 to 9.

class Solution {
private:
void DFS(TreeNode* root, vector<int> &hash, int &ans) {
if (root == NULL)return;
++hash[root->val];

if (root->left == NULL && root->right == NULL) {
int odd = 0;
for (int i = 1; i <= 9; ++i) {
if (hash[i] % 2 == 1) {
++odd;
if (odd > 1) {
break;
}
}
}
if (odd <= 1) {
++ans;
}
--hash[root->val];
return;
}

DFS(root->left, hash, ans);
DFS(root->right, hash, ans);
--hash[root->val];
}
public:
int pseudoPalindromicPaths(TreeNode* root) {
vector<int> hash(10, 0);
int ans = 0;
DFS(root, hash, ans);
return ans;
}
};


# LeetCode Maximum Number of Vowels in a Substring of Given Length

5417. Maximum Number of Vowels in a Substring of Given Length

Given a string s and an integer k.

Return the maximum number of vowel letters in any substring of s with length k.

Vowel letters in English are (a, e, i, o, u).

Example 1:

Input: s = "abciiidef", k = 3
Output: 3
Explanation: The substring "iii" contains 3 vowel letters.


Example 2:

Input: s = "aeiou", k = 2
Output: 2
Explanation: Any substring of length 2 contains 2 vowels.


Example 3:

Input: s = "leetcode", k = 3
Output: 2
Explanation: "lee", "eet" and "ode" contain 2 vowels.


Example 4:

Input: s = "rhythms", k = 4
Output: 0
Explanation: We can see that s doesn't have any vowel letters.


Example 5:

Input: s = "tryhard", k = 4
Output: 1


Constraints:

• 1 <= s.length <= 10^5
• s consists of lowercase English letters.
• 1 <= k <= s.length

class Solution {
public:
bool IsVol(const char &c) {
return c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u';
}
int maxVowels(string s, int k) {
int ans = 0;
int i = 0, j = k - 1, n = s.size();
for (int k = i; k <= j; ++k) {
if (IsVol(s[k]))++ans;
}
int cur = ans;
while (j < n - 1) {
++j;
if (IsVol(s[j]))++cur;
if (IsVol(s[i]))--cur;
++i;
ans = max(ans, cur);
}
return ans;
}
};

# LeetCode Check If a Word Occurs As a Prefix of Any Word in a Sentence

5416. Check If a Word Occurs As a Prefix of Any Word in a Sentence

Given a sentence that consists of some words separated by a single space, and a searchWord.

You have to check if searchWord is a prefix of any word in sentence.

Return the index of the word in sentence where searchWord is a prefix of this word (1-indexed).

If searchWord is a prefix of more than one word, return the index of the first word (minimum index). If there is no such word return -1.

prefix of a string S is any leading contiguous substring of S.

Example 1:

Input: sentence = "i love eating burger", searchWord = "burg"
Output: 4
Explanation: "burg" is prefix of "burger" which is the 4th word in the sentence.


Example 2:

Input: sentence = "this problem is an easy problem", searchWord = "pro"
Output: 2
Explanation: "pro" is prefix of "problem" which is the 2nd and the 6th word in the sentence, but we return 2 as it's the minimal index.


Example 3:

Input: sentence = "i am tired", searchWord = "you"
Output: -1
Explanation: "you" is not a prefix of any word in the sentence.


Example 4:

Input: sentence = "i use triple pillow", searchWord = "pill"
Output: 4


Example 5:

Input: sentence = "hello from the other side", searchWord = "they"
Output: -1


Constraints:

• 1 <= sentence.length <= 100
• 1 <= searchWord.length <= 10
• sentence consists of lowercase English letters and spaces.
• searchWord consists of lowercase English letters.

class Solution {
public:
int isPrefixOfWord(string sentence, string searchWord) {
int idx = 1, i = 0, j = 0, n = sentence.size();
while (i < n) {
j = i + 1;
while (j < n&&sentence[j] != ' ')++j;
string cur = sentence.substr(i, j - i);
size_t pos = cur.find(searchWord);
if (pos != string::npos&&pos == 0) {
return idx;
}
++idx;
i = j + 1;
}
return -1;
}
};


# LeetCode Longest Continuous Subarray With Absolute Diff Less Than or Equal to Limit

1438. Longest Continuous Subarray With Absolute Diff Less Than or Equal to Limit

Given an array of integers nums and an integer limit, return the size of the longest continuous subarray such that the absolute difference between any two elements is less than or equal to limit.

In case there is no subarray satisfying the given condition return 0.

Example 1:

Input: nums = [8,2,4,7], limit = 4
Output: 2
Explanation: All subarrays are:
[8] with maximum absolute diff |8-8| = 0 <= 4.
[8,2] with maximum absolute diff |8-2| = 6 > 4.
[8,2,4] with maximum absolute diff |8-2| = 6 > 4.
[8,2,4,7] with maximum absolute diff |8-2| = 6 > 4.
[2] with maximum absolute diff |2-2| = 0 <= 4.
[2,4] with maximum absolute diff |2-4| = 2 <= 4.
[2,4,7] with maximum absolute diff |2-7| = 5 > 4.
[4] with maximum absolute diff |4-4| = 0 <= 4.
[4,7] with maximum absolute diff |4-7| = 3 <= 4.
[7] with maximum absolute diff |7-7| = 0 <= 4.
Therefore, the size of the longest subarray is 2.


Example 2:

Input: nums = [10,1,2,4,7,2], limit = 5
Output: 4
Explanation: The subarray [2,4,7,2] is the longest since the maximum absolute diff is |2-7| = 5 <= 5.


Example 3:

Input: nums = [4,2,2,2,4,4,2,2], limit = 0
Output: 3


Constraints:

• 1 <= nums.length <= 10^5
• 1 <= nums[i] <= 10^9
• 0 <= limit <= 10^9

class Solution {
public:
int longestSubarray(vector<int>& nums, int limit) {
int n = nums.size();
int ans = 1; // 最小值是1

for (int i = 0; i < n; ++i) {
vector<int> dp_max(n, 0), dp_min(n, INT_MAX);
dp_max[i] = dp_min[i] = nums[i];
for (int len = 2; len <= n; ++len) {
int j = i + len - 1;
if (j >= n)break;
dp_max[j] = max(dp_max[j - 1], nums[j]);
dp_min[j] = min(dp_min[j - 1], nums[j]);
int diff = dp_max[j] - dp_min[j];
if (diff <= limit) {
ans = max(ans, j - i + 1);
}
else {
break;
}
}
}
return ans;
}
};

class Solution {
public:
int longestSubarray(vector<int>& A, int limit) {
int res = 0, n = A.size(), i = 0, j;
multiset<int> m;
for (j = 0; j < n; ++j) {
m.insert(A[j]);
if (*m.rbegin() - *m.begin() > limit)
m.erase(m.find(A[i++]));
else
res=max(res,j-i+1);
}
return res;
}
};

# LeetCode Check If All 1’s Are at Least Length K Places Away

1437. Check If All 1’s Are at Least Length K Places Away

Given an array nums of 0s and 1s and an integer k, return True if all 1’s are at least k places away from each other, otherwise return False.

Example 1:

Input: nums = [1,0,0,0,1,0,0,1], k = 2
Output: true
Explanation: Each of the 1s are at least 2 places away from each other.


Example 2:

Input: nums = [1,0,0,1,0,1], k = 2
Output: false
Explanation: The second 1 and third 1 are only one apart from each other.

Example 3:

Input: nums = [1,1,1,1,1], k = 0
Output: true


Example 4:

Input: nums = [0,1,0,1], k = 1
Output: true


Constraints:

• 1 <= nums.length <= 10^5
• 0 <= k <= nums.length
• nums[i] is 0 or 1

class Solution {
public:
bool kLengthApart(vector<int>& nums, int k) {
int n = nums.size();
int i = 0, j = 0;
while (i < n) {
while (i < n&&nums[i] == 0)++i;
if (i >= n - 1)break;
j = i + 1;
while (j < n&&nums[j] == 0)++j;
if (j - i - 1 < k)return false;
i = j;
}
return true;
}
};

# LeetCode Destination City

5400. Destination City

You are given the array paths, where paths[i] = [cityAi, cityBi] means there exists a direct path going from cityAi to cityBiReturn the destination city, that is, the city without any path outgoing to another city.

It is guaranteed that the graph of paths forms a line without any loop, therefore, there will be exactly one destination city.

Example 1:

Input: paths = [["London","New York"],["New York","Lima"],["Lima","Sao Paulo"]]
Output: "Sao Paulo"
Explanation: Starting at "London" city you will reach "Sao Paulo" city which is the destination city. Your trip consist of: "London" -> "New York" -> "Lima" -> "Sao Paulo".


Example 2:

Input: paths = [["B","C"],["D","B"],["C","A"]]
Output: "A"
Explanation: All possible trips are:
"D" -> "B" -> "C" -> "A".
"B" -> "C" -> "A".
"C" -> "A".
"A".
Clearly the destination city is "A".


Example 3:

Input: paths = [["A","Z"]]
Output: "Z"


Constraints:

• 1 <= paths.length <= 100
• paths[i].length == 2
• 1 <= cityAi.length, cityBi.length <= 10
• cityAi != cityBi
• All strings consist of lowercase and uppercase English letters and the space character.

class Solution {
public:
string destCity(vector<vector<string>>& paths) {
map<string, pair<int,int>> count;
for (int i = 0; i < paths.size(); ++i) {
string src = paths[i][0], dest = paths[i][1];
++count[src].first; // 出度
++count[dest].second; // 入度
}
for (map<string, pair<int, int>>::iterator it = count.begin(); it != count.end(); ++it) {
if (it->second.first == 0) {
return it->first;
}
}
return "";
}
};

# LeetCode Check If a String Is a Valid Sequence from Root to Leaves Path in a Binary Tree

LeetCode Check If a String Is a Valid Sequence from Root to Leaves Path in a Binary Tree

Given a binary tree where each path going from the root to any leaf form a valid sequence, check if a given string is a valid sequence in such binary tree.

We get the given string from the concatenation of an array of integers arr and the concatenation of all values of the nodes along a path results in a sequence in the given binary tree.

Example 1:

Input: root = [0,1,0,0,1,0,null,null,1,0,0], arr = [0,1,0,1]
Output: true
Explanation:
The path 0 -> 1 -> 0 -> 1 is a valid sequence (green color in the figure).
Other valid sequences are:
0 -> 1 -> 1 -> 0
0 -> 0 -> 0


Example 2:

Input: root = [0,1,0,0,1,0,null,null,1,0,0], arr = [0,0,1]
Output: false
Explanation: The path 0 -> 0 -> 1 does not exist, therefore it is not even a sequence.


Example 3:

Input: root = [0,1,0,0,1,0,null,null,1,0,0], arr = [0,1,1]
Output: false
Explanation: The path 0 -> 1 -> 1 is a sequence, but it is not a valid sequence.


Constraints:

• 1 <= arr.length <= 5000
• 0 <= arr[i] <= 9
• Each node’s value is between [0 – 9].

class Solution {
public:
bool dfs(TreeNode* root, vector<int>& arr, int idx) {
int n = arr.size();
if (idx >= n)return false;
if (root->val == arr[idx] && root->left == NULL && root->right == NULL && idx == n - 1)return true;
if (root->val != arr[idx])return false;
bool left = false, right = false;
if (root->left != NULL)left = dfs(root->left, arr, idx + 1);
if (root->right != NULL)right = dfs(root->right, arr, idx + 1);
return left || right;
}
bool isValidSequence(TreeNode* root, vector<int>& arr) {
if (root == NULL)return false;
return dfs(root, arr, 0);
}
};