Given a stringContinue reading “[Leetcode]1520. Maximum Number of Non-Overlapping Substrings”`s`

of lowercase letters, you need to find the maximum number ofnon-emptysubstrings of`s`

that meet the following conditions: The substrings do not overlap, that is for any two substrings`s[i..j]`

and`s[k..l]`

, either`j < k`

or`i > l`

is true. A substring that contains a certain character`c`

must also contain all occurrences of`c`

. Findthe maximum number of substrings that meet the above conditions. If there are multiple solutions with the same number of substrings,return the one with minimum total length.It can be shown that there exists a unique solution of minimum total length. Notice that you can return the substrings inanyorder.

## [Leetcode]1508. Range Sum of Sorted Subarray Sums

Given the arrayContinue reading “[Leetcode]1508. Range Sum of Sorted Subarray Sums”`nums`

consisting of`n`

positive integers. You computed the sum of all non-empty continous subarrays from the array and then sort them in non-decreasing order, creating a new array of`n * (n + 1) / 2`

numbers.Return the sum of the numbers from index`left`

to index`right`

(indexed from 1), inclusive, in the new array.Since the answer can be a huge number return it modulo 10^9 + 7.

## [Leetcode]1513. Number of Substrings With Only 1s

Given a binary stringContinue reading “[Leetcode]1513. Number of Substrings With Only 1s”`s`

(a string consisting only of '0' and '1's). Return the number of substrings with all characters 1's. Since the answer may be too large, return it modulo 10^9 + 7.Example 1:Input:s = "0110111"Output:9Explanation:There are 9 substring in total with only 1's characters. "1" -> 5 times. "11" -> 3 times. "111" -> 1 time.

## [Leetcode]1514. Path with Maximum Probability

You are given an undirected weighted graph ofContinue reading “[Leetcode]1514. Path with Maximum Probability”`n`

nodes (0-indexed), represented by an edge list where`edges[i] = [a, b]`

is an undirected edge connecting the nodes`a`

and`b`

with a probability of success of traversing that edge`succProb[i]`

. Given two nodes`start`

and`end`

, find the path with the maximum probability of success to go from`start`

to`end`

and return its success probability. If there is no path from`start`

to`end`

,return 0.Example 1:Input:n = 3, edges = [[0,1],[1,2],[0,2]], succProb = [0.5,0.5,0.2], start = 0, end = 2Output:0.25000

## [Leetcode]1498. Number of Subsequences That Satisfy the Given Sum Condition

Given an array of integersContinue reading “[Leetcode]1498. Number of Subsequences That Satisfy the Given Sum Condition”`nums`

and an integer`target`

. Return the number ofnon-emptysubsequences of`nums`

such that the sum of the minimum and maximum element on it is less or equal than`target`

. Since the answer may be too large, return it modulo 10^9 + 7.Input:nums = [3,3,6,8], target = 10Output:6Explanation:There are 6 subsequences that satisfy the condition. (nums can have repeated numbers). [3] , [3] , [3,3], [3,6] , [3,6] , [3,3,6]

## [Leetcode]1497. Check If Array Pairs Are Divisible by k

Given an array of integersContinue reading “[Leetcode]1497. Check If Array Pairs Are Divisible by k”`arr`

of even length`n`

and an integer`k`

. We want to divide the array into exactly`n / 2`

pairs such that the sum of each pair is divisible by`k`

. ReturnTrueIf you can find a way to do that orFalseotherwise.Example 1:Input:arr = [1,2,3,4,5,10,6,7,8,9], k = 5Output:trueExplanation:Pairs are (1,9),(2,8),(3,7),(4,6) and (5,10).

## [Leetcode problems]1488. Avoid Flood in The City

Your country has an infinite number of lakes. Initially, all the lakes are empty, but when it rains over theContinue reading “[Leetcode problems]1488. Avoid Flood in The City”`nth`

lake, the`nth`

lake becomes full of water. If it rains over a lake which isfull of water, there will be aflood. Your goal is to avoid the flood in any lake. Given an integer array`rains`

where:`rains[i] > 0`

means there will be rains over the`rains[i]`

lake.`rains[i] == 0`

means there are no rains this day and you can chooseone lakethis day anddry it. Returnan arraywhere:`ans`

`ans.length == rains.length`

`ans[i] == -1`

if`rains[i] > 0`

.`ans[i]`

is the lake you choose to dry in the`ith`

day if`rains[i] == 0`

. If there are multiple valid answers returnanyof them. If it is impossible to avoid flood returnan empty array. Notice that if you chose to dry a full lake, it becomes empty, but if you chose to dry an empty lake, nothing changes. (see example 4)Example 1:Input:rains = [1,2,3,4]Output:[-1,-1,-1,-1]Example 2:Input:rains = [1,2,0,0,2,1]Output:[-1,-1,2,1,-1,-1]

## [Leetcode problems]1482. Minimum Number of Days to Make m Bouquets

Given an integer arrayContinue reading “[Leetcode problems]1482. Minimum Number of Days to Make m Bouquets”`bloomDay`

, an integer`m`

and an integer`k`

. We need to make`m`

bouquets. To make a bouquet, you need to use`k`

adjacent flowersfrom the garden. The garden consists of`n`

flowers, the`ith`

flower will bloom in the`bloomDay[i]`

and then can be used inexactly onebouquet. Returnthe minimum number of daysyou need to wait to be able to make`m`

bouquets from the garden. If it is impossible to make`m`

bouquets return-1.Example 1:Input:bloomDay = [1,10,3,10,2], m = 3, k = 1Output:3Explanation:Let's see what happened in the first three days. x means flower bloomed and _ means flower didn't bloom in the garden. We need 3 bouquets each should contain 1 flower. After day 1: [x, _, _, _, _] // we can only make one bouquet. After day 2: [x, _, _, _, x] // we can only make two bouquets. After day 3: [x, _, x, _, x] // we can make 3 bouquets. The answer is 3.