Huahua’s Tech Road

花花酱 LeetCode 1763. Longest Nice Substring

By zxi on February 20, 2021

A string s is nice if, for every letter of the alphabet that s contains, it appears both in uppercase and lowercase. For example, "abABB" is nice because 'A' and 'a' appear, and 'B' and 'b' appear. However, "abA" is not because 'b' appears, but 'B' does not.

Given a string s, return the longest substring of s that is nice. If there are multiple, return the substring of the earliest occurrence. If there are none, return an empty string.

Example 1:

Input: s = "YazaAay"
Output: "aAa"
Explanation: "aAa" is a nice string because 'A/a' is the only letter of the alphabet in s, and both 'A' and 'a' appear.
"aAa" is the longest nice substring.

Example 2:

Input: s = "Bb"
Output: "Bb"
Explanation: "Bb" is a nice string because both 'B' and 'b' appear. The whole string is a substring.

Example 3:

Input: s = "c"
Output: ""
Explanation: There are no nice substrings.

Example 4:

Input: s = "dDzeE"
Output: "dD"
Explanation: Both "dD" and "eE" are the longest nice substrings.
As there are multiple longest nice substrings, return "dD" since it occurs earlier.

Constraints:

1 <= s.length <= 100
s consists of uppercase and lowercase English letters.

Solution: Brute Force

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

C++

class Solution {

public:

string longestNiceSubstring(string_view s) {

const int n = s.length();

auto isNice = [](string_view s) {

vector<int> u(26), l(26);

for (int c : s)

if (isupper(c)) u[c - 'A'] = 1;

else l[c - 'a'] = 1;

return u == l;

};

string_view ans;

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

for (int j = i + 1; j < n; ++j) {

string_view ss = s.substr(i, j - i + 1);

if (isNice(ss) && ss.length() > ans.length())

ans = ss;

}

return string(ans);

}

};

Optimized 1:

Time complexity: O(n^2*26)
Space complexity: O(1)

C++

class Solution {

public:

string longestNiceSubstring(string_view s) {

const int n = s.length();

string_view ans;

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

vector<int> u(26), l(26);

for (int j = i; j < n; ++j) {

const char c = s[j];

if (isupper(c)) u[c - 'A'] = 1;

else l[c - 'a'] = 1;

if (u == l && j - i + 1 > ans.length())

ans = s.substr(i, j - i + 1);

}

return string(ans);

}

};

花花酱 LeetCode 1761. Minimum Degree of a Connected Trio in a Graph

By zxi on February 13, 2021

You are given an undirected graph. You are given an integer n which is the number of nodes in the graph and an array edges, where each edges[i] = [u_i, v_i] indicates that there is an undirected edge between u_i and v_i.

A connected trio is a set of three nodes where there is an edge between every pair of them.

The degree of a connected trio is the number of edges where one endpoint is in the trio, and the other is not.

Return the minimum degree of a connected trio in the graph, or -1 if the graph has no connected trios.

Example 1:

Input: n = 6, edges = [[1,2],[1,3],[3,2],[4,1],[5,2],[3,6]]
Output: 3
Explanation: There is exactly one trio, which is [1,2,3]. The edges that form its degree are bolded in the figure above.

Example 2:

Input: n = 7, edges = [[1,3],[4,1],[4,3],[2,5],[5,6],[6,7],[7,5],[2,6]]
Output: 0
Explanation: There are exactly three trios:
1) [1,4,3] with degree 0.
2) [2,5,6] with degree 2.
3) [5,6,7] with degree 2.

Constraints:

2 <= n <= 400
edges[i].length == 2
1 <= edges.length <= n * (n-1) / 2
1 <= u_i, v_i <= n
u_i!= v_i
There are no repeated edges.

Solution: Brute Force

Try all possible Trios.

Time complexity: O(n^3)
Space complexity: O(n^2)

C++

// Author: Huahua

class Solution {

public:

int minTrioDegree(int n, vector<vector<int>>& edges) {

vector<bitset<400>> g(n);

for (const auto& e : edges) {

g[e[0] - 1].set(e[1] - 1);

g[e[1] - 1].set(e[0] - 1);

}

size_t ans = INT_MAX;

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

for (int j = i + 1; j < n; ++j)

if (g[i][j])

for (int k = j + 1; k < n; ++k)

if (g[i][k] && g[j][k])

ans = min(ans, g[i].count() + g[j].count() + g[k].count() - 6);

return ans == INT_MAX ? -1 : ans;

}

};

花花酱 LeetCode 1760. Minimum Limit of Balls in a Bag

By zxi on February 13, 2021

You are given an integer array nums where the i^th bag contains nums[i] balls. You are also given an integer maxOperations.

You can perform the following operation at most maxOperations times:

Take any bag of balls and divide it into two new bags with a positive number of balls.
- For example, a bag of 5 balls can become two new bags of 1 and 4 balls, or two new bags of 2 and 3 balls.

Your penalty is the maximum number of balls in a bag. You want to minimize your penalty after the operations.

Return the minimum possible penalty after performing the operations.

Example 1:

Input: nums = [9], maxOperations = 2
Output: 3
Explanation: 
- Divide the bag with 9 balls into two bags of sizes 6 and 3. [9] -> [6,3].
- Divide the bag with 6 balls into two bags of sizes 3 and 3. [6,3] -> [3,3,3].
The bag with the most number of balls has 3 balls, so your penalty is 3 and you should return 3.

Example 2:

Input: nums = [2,4,8,2], maxOperations = 4
Output: 2
Explanation:
- Divide the bag with 8 balls into two bags of sizes 4 and 4. [2,4,8,2] -> [2,4,4,4,2].
- Divide the bag with 4 balls into two bags of sizes 2 and 2. [2,4,4,4,2] -> [2,2,2,4,4,2].
- Divide the bag with 4 balls into two bags of sizes 2 and 2. [2,2,2,4,4,2] -> [2,2,2,2,2,4,2].
- Divide the bag with 4 balls into two bags of sizes 2 and 2. [2,2,2,2,2,4,2] -> [2,2,2,2,2,2,2,2].
The bag with the most number of balls has 2 balls, so your penalty is 2 an you should return 2.

Example 3:

Input: nums = [7,17], maxOperations = 2
Output: 7

Constraints:

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

Solution: Binary Search

Find the smallest penalty that requires less or equal ops than max_ops.

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

C++

// Author: Huahua

class Solution {

public:

int minimumSize(vector<int>& nums, int maxOperations) {

int l = 1, r = *max_element(begin(nums), end(nums));

while (l < r) {

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

int count = 0;

for (int x : nums)

count += (x - 1) / m;

if (count <= maxOperations)

r = m;

else

l = m + 1;

}

return l;

}

};

花花酱 LeetCode 1759. Count Number of Homogenous Substrings

By zxi on February 13, 2021

Given a string s, return the number of homogenous substrings of s. Since the answer may be too large, return it modulo 10⁹ + 7.

A string is homogenous if all the characters of the string are the same.

A substring is a contiguous sequence of characters within a string.

Example 1:

Input: s = "abbcccaa"
Output: 13
Explanation: The homogenous substrings are listed as below:
"a"   appears 3 times.
"aa"  appears 1 time.
"b"   appears 2 times.
"bb"  appears 1 time.
"c"   appears 3 times.
"cc"  appears 2 times.
"ccc" appears 1 time.
3 + 1 + 2 + 1 + 3 + 2 + 1 = 13.

Example 2:

Input: s = "xy"
Output: 2
Explanation: The homogenous substrings are "x" and "y".

Example 3:

Input: s = "zzzzz"
Output: 15

Constraints:

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

Solution: Counting

Let m be the length of the longest homogenous substring, # of homogenous substring is m * (m + 1) / 2.
e.g. aaabb
“aaa” => m = 3, # = 3 * (3 + 1) / 2 = 6
“bb” => m = 2, # = 2 * (2+1) / 2 = 3
Total = 6 + 3 = 9

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

C++

// Author: Huahua

class Solution {

public:

int countHomogenous(string s) {

constexpr int kMod = 1e9 + 7;

const int n = s.length();

long ans = 0;

for (long i = 0, j = 0; i < n; i = j) {

while (j < n && s[i] == s[j]) ++j;

ans += (j - i) * (j - i + 1) / 2;

}

return ans % kMod;

}

};

花花酱 LeetCode 1758. Minimum Changes To Make Alternating Binary String

By zxi on February 13, 2021

You are given a string s consisting only of the characters '0' and '1'. In one operation, you can change any '0' to '1' or vice versa.

The string is called alternating if no two adjacent characters are equal. For example, the string "010" is alternating, while the string "0100" is not.

Return the minimum number of operations needed to make s alternating.

Example 1:

Input: s = "0100"
Output: 1
Explanation: If you change the last character to '1', s will be "0101", which is alternating.

Example 2:

Input: s = "10"
Output: 0
Explanation: s is already alternating.

Example 3:

Input: s = "1111"
Output: 2
Explanation: You need two operations to reach "0101" or "1010".

Constraints:

1 <= s.length <= 10⁴
s[i] is either '0' or '1'.

Solution: Two Counters

The final string is either 010101… or 101010…
We just need two counters to record the number of changes needed to transform the original string to those two final strings.

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

C++

// Author: Huahua

class Solution {

public:

int minOperations(string s) {

int c1 = 0, c2 = 0;

for (int i = 0; i < s.length(); ++i) {

c1 += (s[i] - '0' == i % 2);

c2 += (s[i] - '0' != i % 2);

}

return min(c1, c2);

}

};

Huahua's Tech Road

花花酱 LeetCode 1763. Longest Nice Substring

Solution: Brute Force

C++

C++

花花酱 LeetCode 1761. Minimum Degree of a Connected Trio in a Graph

Solution: Brute Force

C++

花花酱 LeetCode 1760. Minimum Limit of Balls in a Bag

Solution: Binary Search

C++

花花酱 LeetCode 1759. Count Number of Homogenous Substrings

C++

花花酱 LeetCode 1758. Minimum Changes To Make Alternating Binary String

Solution: Two Counters

C++