Huahua’s Tech Road

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

}

};

花花酱 LeetCode 2389. Longest Subsequence With Limited Sum

By zxi on September 1, 2022

You are given an integer array nums of length n, and an integer array queries of length m.

Return an array answer of length m where answer[i] is the maximum size of a subsequence that you can take from nums such that the sum of its elements is less than or equal to queries[i].

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,5,2,1], queries = [3,10,21]
Output: [2,3,4]
Explanation: We answer the queries as follows:
- The subsequence [2,1] has a sum less than or equal to 3. It can be proven that 2 is the maximum size of such a subsequence, so answer[0] = 2.
- The subsequence [4,5,1] has a sum less than or equal to 10. It can be proven that 3 is the maximum size of such a subsequence, so answer[1] = 3.
- The subsequence [4,5,2,1] has a sum less than or equal to 21. It can be proven that 4 is the maximum size of such a subsequence, so answer[2] = 4.

Example 2:

Input: nums = [2,3,4,5], queries = [1]
Output: [0]
Explanation: The empty subsequence is the only subsequence that has a sum less than or equal to 1, so answer[0] = 0.

Constraints:

n == nums.length
m == queries.length
1 <= n, m <= 1000
1 <= nums[i], queries[i] <= 10⁶

Solution: Sort + PrefixSum + Binary Search

Time complexity: O(nlogn + mlogn)
Space complexity: O(1)

C++

// Author: Huahua

class Solution {

public:

vector<int> answerQueries(vector<int>& nums, vector<int>& queries) {

sort(begin(nums), end(nums));

partial_sum(begin(nums), end(nums), begin(nums));

vector<int> ans;

for (int q : queries)

ans.push_back(upper_bound(begin(nums), end(nums), q) - begin(nums));

return ans;

}

};

Huahua's Tech Road

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

花花酱 LeetCode 2389. Longest Subsequence With Limited Sum

Solution: Sort + PrefixSum + Binary Search

C++