loading...

Daily Coding Challenge #87

wingkwong profile image Wing-Kam ・5 min read

About

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.


/*
Make The String Great

Given a string s of lower and upper case English letters.

A good string is a string which doesn't have two adjacent characters s[i] and s[i + 1] where:

0 <= i <= s.length - 2
s[i] is a lower-case letter and s[i + 1] is the same letter but in upper-case or vice-versa.
To make the string good, you can choose two adjacent characters that make the string bad and remove them. You can keep doing this until the string becomes good.

Return the string after making it good. The answer is guaranteed to be unique under the given constraints.

Notice that an empty string is also good.
*/

class Solution {
public:
    string makeGood(string s) {
        // stack approach
        stack<char> st;
        for(char c:s){
            int skip=0;
            while(st.size()&& c!=st.top()&&tolower(c)==tolower(st.top())){
                st.pop();
                skip=1;
                break;
            }
            if(!skip) st.push(c);
        }
        string ans;
        while(st.size()){
            ans=st.top()+ans;
            st.pop();
        }
        return ans;
    }
};

class Solution2 {
public:
    string makeGood(string s) {
        // brute force
        int sz = 0 ;
        while(sz!=s.size()){
            sz=s.size();
            for(int i=0;i+1<s.size();i++){
                if(s[i]!=s[i+1]&&tolower(s[i])==tolower(s[i+1])){
                    s=s.substr(0,i)+s.substr(i+2);
                }
            }
        }
        return s;
    }
};

/*
Find Kth Bit in Nth Binary String

Given two positive integers n and k, the binary string  Sn is formed as follows:

S1 = "0"
Si = Si-1 + "1" + reverse(invert(Si-1)) for i > 1
Where + denotes the concatenation operation, reverse(x) returns the reversed string x, and invert(x) inverts all the bits in x (0 changes to 1 and 1 changes to 0).

For example, the first 4 strings in the above sequence are:

S1 = "0"
S2 = "011"
S3 = "0111001"
S4 = "011100110110001"
Return the kth bit in Sn. It is guaranteed that k is valid for the given n.

Example 1:

Input: n = 3, k = 1
Output: "0"
Explanation: S3 is "0111001". The first bit is "0".
Example 2:

Input: n = 4, k = 11
Output: "1"
Explanation: S4 is "011100110110001". The 11th bit is "1".
Example 3:

Input: n = 1, k = 1
Output: "0"
Example 4:

Input: n = 2, k = 3
Output: "1"


Constraints:

1 <= n <= 20
1 <= k <= 2n - 1
*/

class Solution {
public:

    char findKthBit(int n, int k) {
        string s[n];
        s[0]="0";
        for(int i=1;i<n;i++){
            // Si = Si-1 + "1" + reverse(invert(Si-1))
            string prev=s[i-1];
            s[i]=prev+"1";
            for(char &c:prev) c^=1;
            reverse(prev.begin(),prev.end());
            s[i]+=prev;
        }
        return s[n-1][k-1];
    }
};

/*
Maximum Number of Non-Overlapping Subarrays With Sum Equals Target

Given an array nums and an integer target.

Return the maximum number of non-empty non-overlapping subarrays such that the sum of values in each subarray is equal to target.

Example 1:

Input: nums = [1,1,1,1,1], target = 2
Output: 2
Explanation: There are 2 non-overlapping subarrays [1,1,1,1,1] with sum equals to target(2).
Example 2:

Input: nums = [-1,3,5,1,4,2,-9], target = 6
Output: 2
Explanation: There are 3 subarrays with sum equal to 6.
([5,1], [4,2], [3,5,1,4,2,-9]) but only the first 2 are non-overlapping.
Example 3:

Input: nums = [-2,6,6,3,5,4,1,2,8], target = 10
Output: 3
Example 4:

Input: nums = [0,0,0], target = 0
Output: 3

Constraints:

1 <= nums.length <= 10^5
-10^4 <= nums[i] <= 10^4
0 <= target <= 10^6
*/

class Solution {
public:
    int maxNonOverlapping(vector<int>& nums, int target) {
        // intuition : 
        // - use prefix sum in hash map & look for sum-target
        // - use right to check if two arrays are overlapping or not
        unordered_map<int,int> m;
        m[0]=-1;
        int sum=0,right=-1,ans=0;
        for(int left=0;left<nums.size();left++){
            sum+=nums[left];
            if(m.count(sum-target)){
                int l = m[sum-target];
                if(right<=l){
                    ans++;
                    right=left;
                }
            }
            m[sum]=left;
        }
        return ans;
    }
};

/*
Minimum Cost to Cut a Stick

Given a wooden stick of length n units. The stick is labelled from 0 to n. For example, a stick of length 6 is labelled as follows:


Given an integer array cuts where cuts[i] denotes a position you should perform a cut at.

You should perform the cuts in order, you can change the order of the cuts as you wish.

The cost of one cut is the length of the stick to be cut, the total cost is the sum of costs of all cuts. When you cut a stick, it will be split into two smaller sticks (i.e. the sum of their lengths is the length of the stick before the cut). Please refer to the first example for a better explanation.

Return the minimum total cost of the cuts.

Example 1:

Input: n = 7, cuts = [1,3,4,5]
Output: 16
Explanation: Using cuts order = [1, 3, 4, 5] as in the input leads to the following scenario:

The first cut is done to a rod of length 7 so the cost is 7. The second cut is done to a rod of length 6 (i.e. the second part of the first cut), the third is done to a rod of length 4 and the last cut is to a rod of length 3. The total cost is 7 + 6 + 4 + 3 = 20.
Rearranging the cuts to be [3, 5, 1, 4] for example will lead to a scenario with total cost = 16 (as shown in the example photo 7 + 4 + 3 + 2 = 16).

Example 2:

Input: n = 9, cuts = [5,6,1,4,2]
Output: 22
Explanation: If you try the given cuts ordering the cost will be 25.
There are much ordering with total cost <= 25, for example, the order [4, 6, 5, 2, 1] has total cost = 22 which is the minimum possible.

Constraints:

2 <= n <= 10^6
1 <= cuts.length <= min(n - 1, 100)
1 <= cuts[i] <= n - 1
All the integers in cuts array are distinct.
*/

class Solution {
public:
    int dp[105][105];
    int dfs(vector<int>& cuts, int i, int j){
        if(j-i<=1) return 0;
        if(dp[i][j]!=-1) return dp[i][j];
        int res=INT_MAX;
        for(int k=i+1;k<j;k++){
            res=min(res,cuts[j]-cuts[i]+dfs(cuts,i,k)+dfs(cuts,k,j));
        }
        return dp[i][j]=res;
    }
    int minCost(int n, vector<int>& cuts) {
        // sort the cuts and use dfs to find the min cost
        // use dp[][] to memoise the min cosst for [cuts[i],cuts[j]]
        cuts.emplace_back(0);
        cuts.emplace_back(n);
        sort(cuts.begin(),cuts.end());
        memset(dp,-1,sizeof(dp));
        return dfs(cuts,0,cuts.size()-1);
    }
};

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

GitHub logo wingkwong / leetcode

πŸ† A Collection of my LeetCode Solutions with Explanations πŸ†

GitHub logo wingkwong / hackerrank

πŸ† A Collection of my HackerRank Solutions with Explanations πŸ†

GitHub logo wingkwong / codeforces

πŸ† A Collection of my Codeforces Solutions with Explanations πŸ†

GitHub logo wingkwong / atcoder

πŸ† A Collection of my AtCoder Solutions with Explanations πŸ†

Posted on by:

wingkwong profile

Wing-Kam

@wingkwong

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

Discussion

markdown guide