# Daily Coding Challenge #7

This is a series of Daily Coding Challenge. Each day I show a few solutions written in C++. The questions are from coding practice/contest sites such as HackerRank, LeetCode, Codeforces, Atcoder and etc.

``````/*
LeetCode - Consecutive Characters

Given a string s, the power of the string is the maximum length of a non-empty substring that contains only one unique character.

Return the power of the string.

Example 1:

Input: s = "leetcode"
Output: 2
Explanation: The substring "ee" is of length 2 with the character 'e' only.
Example 2:

Input: s = "abbcccddddeeeeedcba"
Output: 5
Explanation: The substring "eeeee" is of length 5 with the character 'e' only.
Example 3:

Input: s = "triplepillooooow"
Output: 5
Example 4:

Input: s = "hooraaaaaaaaaaay"
Output: 11
Example 5:

Input: s = "tourist"
Output: 1
*/

class Solution {
public:
int maxPower(string s) {
int ans=1,cnt=1;
char cur=s[0];
// traverse each character
for(int i=1;i<s.size();i++){
if(s[i]==cur){
// if it is consecutive, add 1 to the counter
// and check if it s greater than max length
cnt++;
ans=max(ans,cnt);
} else {
// if not, update cur and reset the counter
cur=s[i];
cnt=1;
}
}
return ans;
}
};
``````

``````/*
LeetCode - Simplified Fractions

Given an integer n, return a list of all simplified fractions between 0 and 1 (exclusive) such that the denominator is less-than-or-equal-to n. The fractions can be in any order.

Example 1:

Input: n = 2
Output: ["1/2"]
Explanation: "1/2" is the only unique fraction with a denominator less-than-or-equal-to 2.
Example 2:

Input: n = 3
Output: ["1/2","1/3","2/3"]
Example 3:

Input: n = 4
Output: ["1/2","1/3","1/4","2/3","3/4"]
Explanation: "2/4" is not a simplified fraction because it can be simplified to "1/2".
Example 4:

Input: n = 1
Output: []

Constraints: 1 <= n <= 100
*/

class Solution {
public:
// int helper(int x, int y){
//     int d,xx,yy;
//     d=__gcd(x,y);
//     xx=x/d;
//     yy=y/d;
//     return (xx==x&&yy==y);
// }

vector<string> simplifiedFractions(int n) {
vector<string> ans;
// brute-force approach to find out all answers
for(int i=2;i<=n;i++) {
for(int j=1;j<n;j++){
if(
(i%j==0&&j!=1) ||
(j/i)>=1 ||
!__gcd(i,j)
) continue;
// 20200518: I think it can be further simplified
// check if __gcd(i,j) is 1, if so, j/i would be one of the answers
ans.push_back(to_string(j)+"/"+to_string(i));
}
}
return ans;
}
};

``````

``````/*
LeetCode - Count Good Nodes in Binary Tree

Given a binary tree root, a node X in the tree is named good if in the path from root to X there are no nodes with a value greater than X.

Return the number of good nodes in the binary tree.
*/

/**
* Definition for a binary tree node.
* struct TreeNode {
*     int val;
*     TreeNode *left;
*     TreeNode *right;
*     TreeNode() : val(0), left(nullptr), right(nullptr) {}
*     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
*     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
void dsf(TreeNode* root, int val){
// if root is NULL, return
if(!root) return;
// if the node value is greater than / equal to the max value, increase ans by 1
if(root->val>=val) ans++;
int mx=max(root->val,val);
// pass the max value to left node
dsf(root->left, mx);
// pass the max value to right node
dsf(root->right, mx);
}

int goodNodes(TreeNode* root) {
// simple dsf approach
// record the maximum value along the path from the root to the node
dsf(root, root->val);
return ans;
}
private:
int ans=0;
};
``````

``````/*
LeetCode - Form Largest Integer With Digits That Add up to Target

Given an array of integers cost and an integer target. Return the maximum integer you can paint under the following rules:

The cost of painting a digit (i+1) is given by cost[i] (0 indexed).
The total cost used must be equal to target.
Integer does not have digits 0.
Since the answer may be too large, return it as string.

If there is no way to paint any integer given the condition, return "0".

Example 1:

Input: cost = [4,3,2,5,6,7,2,5,5], target = 9
Output: "7772"
Explanation:  The cost to paint the digit '7' is 2, and the digit '2' is 3. Then cost("7772") = 2*3+ 3*1 = 9. You could also paint "997", but "7772" is the largest number.
Digit    cost
1  ->   4
2  ->   3
3  ->   2
4  ->   5
5  ->   6
6  ->   7
7  ->   2
8  ->   5
9  ->   5
Example 2:

Input: cost = [7,6,5,5,5,6,8,7,8], target = 12
Output: "85"
Explanation: The cost to paint the digit '8' is 7, and the digit '5' is 5. Then cost("85") = 7 + 5 = 12.
Example 3:

Input: cost = [2,4,6,2,4,6,4,4,4], target = 5
Output: "0"
Explanation: It's not possible to paint any integer with total cost equal to target.
Example 4:

Input: cost = [6,10,15,40,40,40,40,40,40], target = 47
Output: "32211"

Constraints:

cost.length == 9
1 <= cost[i] <= 5000
1 <= target <= 5000
*/

class Solution {
public:
// top-down dp approach
string largestNumber(vector<int>& cost, int target) {
if(target==0) return "";
if(target<0) return "0";
if(dp[target].empty()){
dp[target]="0";
// 9 digits
for(int i=1;i<=9;i++){
// build the result string
string res=largestNumber(cost,target-cost[i-1]);
// if res is "0", that means cost[n]>=target, hence we can't take this digit
// if res size plus 1 is greater than the dp[target] size,
if(res!="0"&&res.size()+1>=dp[target].size()){
dp[target]=to_string(i)+res;
}
}
}
return dp[target];
}
private:
string dp[5001] = {};
};

class Solution2 {
public:
string largestNumber(vector<int>& cost, int target) {
vector<string> dp(target+1,"0");
int n=(int)cost.size();
dp[0]="";
for(int i=0;i<n;i++){
for(int j=1;j<=target;j++){
if(
j<cost[i] ||
dp[j-cost[i]]=="0"
) continue;
string s = string(1,'1'+i)+dp[j-cost[i]];
if(
s.size() != dp[j].size() ?
s.size() > dp[j].size() :
s > dp[j]
) dp[j]=s;
}
}
return dp[target];
}
};
``````

The source code is available in corresponding repo below. Star and watch for timely updates!

## wingkwong / atcoder

Posted on by:

### Wing-Kam

Consultant by day. Developer by night. AWS certified. Exploring #CloudNative currently.