Given a parentheses string s containing only the characters '(' and ')'. A parentheses string is balanced if:
Any left parenthesis '(' must have a corresponding two consecutive right parenthesis '))'.
Left parenthesis '(' must go before the corresponding two consecutive right parenthesis '))'.
For example, "())", "())(())))" and "(())())))" are balanced, ")()", "()))" and "(()))" are not balanced.
You can insert the characters ‘(‘ and ‘)’ at any position of the string to balance it if needed.
Return the minimum number of insertions needed to make s balanced.
Example 1:
Input: s = "(()))"
Output: 1
Explanation: The second '(' has two matching '))', but the first '(' has only ')' matching. We need to to add one more ')' at the end of the string to be "(())))" which is balanced.
Example 2:
Input: s = "())"
Output: 0
Explanation: The string is already balanced.
Example 3:
Input: s = "))())("
Output: 3
Explanation: Add '(' to match the first '))', Add '))' to match the last '('.
Example 4:
Input: s = "(((((("
Output: 12
Explanation: Add 12 ')' to balance the string.
Example 5:
Input: s = ")))))))"
Output: 5
Explanation: Add 4 '(' at the beginning of the string and one ')' at the end. The string becomes "(((())))))))".
Constraints:
1 <= s.length <= 10^5
s consists of '(' and ')' only.
Solution: Counting
Count how many close parentheses we need.
if s[i] is ‘)’, we decrease the counter.
if counter becomes negative, means we need to insert ‘(‘
increase ans by 1, increase the counter by 2, we need one more ‘)’
‘)’ -> ‘()’
if s[i] is ‘(‘
if we have an odd counter, means there is a unbalanced ‘)’ e.g. ‘(()(‘, counter is 3
need to insert ‘)’, decrease counter, increase ans
‘(()(‘ -> ‘(())(‘, counter = 2
increase counter by 2, each ‘(‘ needs two ‘)’s. ‘(())(‘ -> counter = 4
Once done, if counter is greater than zero, we need insert that much ‘)s’
Given three integers n, m and k. Consider the following algorithm to find the maximum element of an array of positive integers:
You should build the array arr which has the following properties:
arr has exactly n integers.
1 <= arr[i] <= m where (0 <= i < n).
After applying the mentioned algorithm to arr, the value search_cost is equal to k.
Return the number of ways to build the array arr under the mentioned conditions. As the answer may grow large, the answer must be computed modulo 10^9 + 7.
Example 1:
Input: n = 2, m = 3, k = 1
Output: 6
Explanation: The possible arrays are [1, 1], [2, 1], [2, 2], [3, 1], [3, 2] [3, 3]
Example 2:
Input: n = 5, m = 2, k = 3
Output: 0
Explanation: There are no possible arrays that satisify the mentioned conditions.
Example 3:
Input: n = 9, m = 1, k = 1
Output: 1
Explanation: The only possible array is [1, 1, 1, 1, 1, 1, 1, 1, 1]
Example 4:
Input: n = 50, m = 100, k = 25
Output: 34549172
Explanation: Don't forget to compute the answer modulo 1000000007
Example 5:
Input: n = 37, m = 17, k = 7
Output: 418930126
Constraints:
1 <= n <= 50
1 <= m <= 100
0 <= k <= n
Solution: DP
dp[n][m][k] := ways to build given n,m,k.
dp[n][m][k] = sum(dp[n-1][m][k] + dp[n-1][i-1][k-1] – dp[n-1][i-1][k]), 1 <= i <= m dp[1][m][1] = m dp[n][m][k] = 0 if k < 1 or k > m or k > n
Time complexity: O(n*m^2*k) Space complexity: O(n*m*k)
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
// Author: Huahua
intmem[51][101][51]={0};
classSolution{
public:
intnumOfArrays(intn,intm,intk){
constintkMod=1e9+7;
function<int(int,int,int)>dp=[&dp](int n, int m, int k) {
Given a string s. You should re-order the string using the following algorithm:
Pick the smallest character from s and append it to the result.
Pick the smallest character from s which is greater than the last appended character to the result and append it.
Repeat step 2 until you cannot pick more characters.
Pick the largest character from s and append it to the result.
Pick the largest character from s which is smaller than the last appended character to the result and append it.
Repeat step 5 until you cannot pick more characters.
Repeat the steps from 1 to 6 until you pick all characters from s.
In each step, If the smallest or the largest character appears more than once you can choose any occurrence and append it to the result.
Return the result string after sorting s with this algorithm.
Example 1:
Input: s = "aaaabbbbcccc"
Output: "abccbaabccba"
Explanation: After steps 1, 2 and 3 of the first iteration, result = "abc"
After steps 4, 5 and 6 of the first iteration, result = "abccba"
First iteration is done. Now s = "aabbcc" and we go back to step 1
After steps 1, 2 and 3 of the second iteration, result = "abccbaabc"
After steps 4, 5 and 6 of the second iteration, result = "abccbaabccba"
Example 2:
Input: s = "rat"
Output: "art"
Explanation: The word "rat" becomes "art" after re-ordering it with the mentioned algorithm.
Example 3:
Input: s = "leetcode"
Output: "cdelotee"
Example 4:
Input: s = "ggggggg"
Output: "ggggggg"
Example 5:
Input: s = "spo"
Output: "ops"
Constraints:
1 <= s.length <= 500
s contains only lower-case English letters.
Solution: Counting frequency of each character
Time complexity: O(n * 26) Space complexity: O(26)
Given the array nums, for each nums[i] find out how many numbers in the array are smaller than it. That is, for each nums[i] you have to count the number of valid j's such that j != iandnums[j] < nums[i].
Return the answer in an array.
Example 1:
Input: nums = [8,1,2,2,3]
Output: [4,0,1,1,3]
Explanation:
For nums[0]=8 there exist four smaller numbers than it (1, 2, 2 and 3).
For nums[1]=1 does not exist any smaller number than it.
For nums[2]=2 there exist one smaller number than it (1).
For nums[3]=2 there exist one smaller number than it (1).
For nums[4]=3 there exist three smaller numbers than it (1, 2 and 2).