Huahua’s Tech Road

花花酱 LeetCode 2407. Longest Increasing Subsequence II

By zxi on September 11, 2022

You are given an integer array nums and an integer k.

Find the longest subsequence of nums that meets the following requirements:

The subsequence is strictly increasing and
The difference between adjacent elements in the subsequence is at most k.

Return the length of the longest subsequence that meets the requirements.

A subsequence is an array that can be derived from another array by deleting some or no elements without changing the order of the remaining elements.

Example 1:

Input: nums = [4,2,1,4,3,4,5,8,15], k = 3
Output: 5
Explanation:
The longest subsequence that meets the requirements is [1,3,4,5,8].
The subsequence has a length of 5, so we return 5.
Note that the subsequence [1,3,4,5,8,15] does not meet the requirements because 15 - 8 = 7 is larger than 3.

Example 2:

Input: nums = [7,4,5,1,8,12,4,7], k = 5
Output: 4
Explanation:
The longest subsequence that meets the requirements is [4,5,8,12].
The subsequence has a length of 4, so we return 4.

Example 3:

Input: nums = [1,5], k = 1
Output: 1
Explanation:
The longest subsequence that meets the requirements is [1].
The subsequence has a length of 1, so we return 1.

Constraints:

1 <= nums.length <= 10⁵
1 <= nums[i], k <= 10⁵

Solution: DP + Segment Tree | Max range query

Let dp[i] := length of LIS end with number i.
dp[i] = 1 + max(dp[i-k:i])

Naive dp takes O(n*k) time which will cause TLE.

We can use segment tree to speed up the max range query to log(m), where m is the max value of the array.

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

C++

// Author: Huahua

class Solution {

public:

int lengthOfLIS(vector<int>& nums, int k) {

const int n = *max_element(begin(nums), end(nums));

vector<int> dp(2 * (n + 1));

auto query = [&](int l, int r) -> int {

int ans = 0;

for (l += n, r += n; l < r; l >>= 1, r >>= 1) {

if (l & 1) ans = max(ans, dp[l++]);

if (r & 1) ans = max(ans, dp[--r]);

}

return ans;

};

auto update = [&](int i, int val) -> void {

dp[i += n] = val;

while (i > 1) {

i >>= 1;

dp[i] = max(dp[i * 2], dp[i * 2 + 1]);

}

};

int ans = 0;

for (int x : nums) {

int cur = 1 + query(max(1, x - k), x);

update(x, cur);

ans = max(ans, cur);

}

return ans;

}

};

花花酱 LeetCode 2405. Optimal Partition of String

By zxi on September 11, 2022

Given a string s, partition the string into one or more substrings such that the characters in each substring are unique. That is, no letter appears in a single substring more than once.

Return the minimum number of substrings in such a partition.

Note that each character should belong to exactly one substring in a partition.

Example 1:

Input: s = "abacaba"
Output: 4
Explanation:
Two possible partitions are ("a","ba","cab","a") and ("ab","a","ca","ba").
It can be shown that 4 is the minimum number of substrings needed.

Example 2:

Input: s = "ssssss"
Output: 6
Explanation:
The only valid partition is ("s","s","s","s","s","s").

Constraints:

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

Solution: Greedy

Extend the cur string as long as possible unless a duplicate character occurs.

You can use hashtable / array or bitmask to mark whether a character has been seen so far.

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

C++

// Author: Huahua

class Solution {

public:

int partitionString(string s) {

unordered_set<char> m;

int ans = 0;

for (char c : s) {

if (m.insert(c).second) continue;

m.clear();

m.insert(c);

++ans;

}

return ans + 1;

}

};

C++

// Author: Huahua

class Solution {

public:

int partitionString(string s) {

vector<int> m(26);

int ans = 0;

for (char c : s) {

if (++m[c - 'a'] == 1) continue;

fill(begin(m), end(m), 0);

m[c - 'a'] = 1;

++ans;

}

return ans + 1;

}

};

C++

// Author: Huahua

class Solution {

public:

int partitionString(string s) {

int mask = 0;

int ans = 0;

for (char c : s) {

if (mask & (1 << (c - 'a'))) {

mask = 0;

++ans;

}

mask |= 1 << (c - 'a');

}

return ans + 1;

}

};

花花酱 LeetCode 2404. Most Frequent Even Element

By zxi on September 11, 2022

Given an integer array nums, return the most frequent even element.

If there is a tie, return the smallest one. If there is no such element, return -1.

Example 1:

Input: nums = [0,1,2,2,4,4,1]
Output: 2
Explanation:
The even elements are 0, 2, and 4. Of these, 2 and 4 appear the most.
We return the smallest one, which is 2.

Example 2:

Input: nums = [4,4,4,9,2,4]
Output: 4
Explanation: 4 is the even element appears the most.

Example 3:

Input: nums = [29,47,21,41,13,37,25,7]
Output: -1
Explanation: There is no even element.

Constraints:

1 <= nums.length <= 2000
0 <= nums[i] <= 10⁵

Solution: Hashtable

Use a hashtable to store the frequency of even numbers.

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

C++

// Author: Huahua

class Solution {

public:

int mostFrequentEven(vector<int>& nums) {

unordered_map<int, int> m;

int ans = -1;

int best = 0;

for (int x : nums) {

if (x & 1) continue;

int cur = ++m[x];

if (cur > best) {

best = cur;

ans = x;

} else if (cur == best && x < ans) {

ans = x;

}

return ans;

}

};

花花酱 LeetCode 2396. Strictly Palindromic Number

By zxi on September 7, 2022

An integer n is strictly palindromic if, for every base b between 2 and n - 2 (inclusive), the string representation of the integer n in base b is palindromic.

Given an integer n, return true if n is strictly palindromic and false otherwise.

A string is palindromic if it reads the same forward and backward.

Example 1:

Input: n = 9
Output: false
Explanation: In base 2: 9 = 1001 (base 2), which is palindromic.
In base 3: 9 = 100 (base 3), which is not palindromic.
Therefore, 9 is not strictly palindromic so we return false.
Note that in bases 4, 5, 6, and 7, n = 9 is also not palindromic.

Example 2:

Input: n = 4
Output: false
Explanation: We only consider base 2: 4 = 100 (base 2), which is not palindromic.
Therefore, we return false.

Constraints:

4 <= n <= 10⁵

Solution: Just return false

No such number.

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

C++

// Author: Huahua

class Solution {

public:

bool isStrictlyPalindromic(int n) {

return false;

}

};

花花酱 LeetCode 2395. Find Subarrays With Equal Sum

By zxi on September 7, 2022

Given a 0-indexed integer array nums, determine whether there exist two subarrays of length 2 with equal sum. Note that the two subarrays must begin at different indices.

Return true if these subarrays exist, and false otherwise.

A subarray is a contiguous non-empty sequence of elements within an array.

Example 1:

Input: nums = [4,2,4]
Output: true
Explanation: The subarrays with elements [4,2] and [2,4] have the same sum of 6.

Example 2:

Input: nums = [1,2,3,4,5]
Output: false
Explanation: No two subarrays of size 2 have the same sum.

Example 3:

Input: nums = [0,0,0]
Output: true
Explanation: The subarrays [nums[0],nums[1]] and [nums[1],nums[2]] have the same sum of 0. 
Note that even though the subarrays have the same content, the two subarrays are considered different because they are in different positions in the original array.

Constraints:

2 <= nums.length <= 1000
-10⁹ <= nums[i] <= 10⁹

Solution: Hashset

Use a hashset to track all the sums seen so far.

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

C++

// Author: Huahua

class Solution {

public:

bool findSubarrays(vector<int>& nums) {

unordered_set<int> s;

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

if (!s.emplace(nums[i] + nums[i - 1]).second) return true;

return false;

}

};

Huahua's Tech Road

花花酱 LeetCode 2407. Longest Increasing Subsequence II

Solution: DP + Segment Tree | Max range query

C++

花花酱 LeetCode 2405. Optimal Partition of String

Solution: Greedy

C++

C++

C++

花花酱 LeetCode 2404. Most Frequent Even Element

Solution: Hashtable

C++

花花酱 LeetCode 2396. Strictly Palindromic Number

Solution: Just return false

C++

花花酱 LeetCode 2395. Find Subarrays With Equal Sum

Solution: Hashset

C++