loading...

Daily Coding Challenge #116

wingkwong profile image Wing-Kam ・4 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.


/*
Replace All ?'s to Avoid Consecutive Repeating Characters
https://leetcode.com/problems/replace-all-s-to-avoid-consecutive-repeating-characters/

Given a string s containing only lower case English letters and the '?' character, convert all the '?' characters into lower case letters such that the final string does not contain any consecutive repeating characters. You cannot modify the non '?' characters.

It is guaranteed that there are no consecutive repeating characters in the given string except for '?'.

Return the final string after all the conversions (possibly zero) have been made. If there is more than one solution, return any of them. It can be shown that an answer is always possible with the given constraints.



Example 1:

Input: s = "?zs"
Output: "azs"
Explanation: There are 25 solutions for this problem. From "azs" to "yzs", all are valid. Only "z" is an invalid modification as the string will consist of consecutive repeating characters in "zzs".
Example 2:

Input: s = "ubv?w"
Output: "ubvaw"
Explanation: There are 24 solutions for this problem. Only "v" and "w" are invalid modifications as the strings will consist of consecutive repeating characters in "ubvvw" and "ubvww".
Example 3:

Input: s = "j?qg??b"
Output: "jaqgacb"
Example 4:

Input: s = "??yw?ipkj?"
Output: "acywaipkja"


Constraints:

1 <= s.length <= 100

s contains only lower case English letters and '?'.

*/

class Solution {
public:
    string modifyString(string s) {
        int n=s.size();
        for(int i=0;i<n;i++){
            int j=0; // max 3 characters
            if(s[i]=='?'){
                while(
                    // if the current character is same as the previous one
                    i>0&&(('a'+j)%26)+'a'==s[i-1] || 
                    // if the current character is same as the next one
                    i<n&&(('a'+j)%26)+'a'==s[i+1] 
                ) j++;
                // update s[i]
                s[i]=(('a'+j)%26)+'a'; 
            }
        }
        return s;
    }
};

/*
Number of Ways Where Square of Number Is Equal to Product of Two Numbers
https://leetcode.com/problems/number-of-ways-where-square-of-number-is-equal-to-product-of-two-numbers/

Given two arrays of integers nums1 and nums2, return the number of triplets formed (type 1 and type 2) under the following rules:

Type 1: Triplet (i, j, k) if nums1[i]2 == nums2[j] * nums2[k] where 0 <= i < nums1.length and 0 <= j < k < nums2.length.
Type 2: Triplet (i, j, k) if nums2[i]2 == nums1[j] * nums1[k] where 0 <= i < nums2.length and 0 <= j < k < nums1.length.


Example 1:

Input: nums1 = [7,4], nums2 = [5,2,8,9]
Output: 1
Explanation: Type 1: (1,1,2), nums1[1]^2 = nums2[1] * nums2[2]. (4^2 = 2 * 8). 
Example 2:

Input: nums1 = [1,1], nums2 = [1,1,1]
Output: 9
Explanation: All Triplets are valid, because 1^2 = 1 * 1.
Type 1: (0,0,1), (0,0,2), (0,1,2), (1,0,1), (1,0,2), (1,1,2).  nums1[i]^2 = nums2[j] * nums2[k].
Type 2: (0,0,1), (1,0,1), (2,0,1). nums2[i]^2 = nums1[j] * nums1[k].
Example 3:

Input: nums1 = [7,7,8,3], nums2 = [1,2,9,7]
Output: 2
Explanation: There are 2 valid triplets.
Type 1: (3,0,2).  nums1[3]^2 = nums2[0] * nums2[2].
Type 2: (3,0,1).  nums2[3]^2 = nums1[0] * nums1[1].
Example 4:

Input: nums1 = [4,7,9,11,23], nums2 = [3,5,1024,12,18]
Output: 0
Explanation: There are no valid triplets.


Constraints:

1 <= nums1.length, nums2.length <= 1000
1 <= nums1[i], nums2[i] <= 10^5
*/

class Solution {
public:
    int numTriplets(vector<int>& nums1, vector<int>& nums2) {
        int ans=0;
        map<long long, int> nums1SQ, nums1JK, nums2SQ, nums2JK;
        // calculate all possible answers and store them into map
        // search each value to see if it matches
        for(int j=0;j<nums1.size();j++){
            for(int k=j+1;k<nums1.size();k++){
                nums1JK[(long long)nums1[j]*nums1[k]]++;
            }
            nums1SQ[(long long)nums1[j]*nums1[j]]++;
        }
        for(int j=0;j<nums2.size();j++){
            for(int k=j+1;k<nums2.size();k++){
                nums2JK[(long long)nums2[j]*nums2[k]]++;
            }
            nums2SQ[(long long)nums2[j]*nums2[j]]++;
        }
        for(auto x: nums1SQ) ans+=nums2JK[x.first]*x.second;
        for(auto x: nums2SQ) ans+=nums1JK[x.first]*x.second;
        return ans;
    }
};

/*
Minimum Deletion Cost to Avoid Repeating Letters
https://leetcode.com/problems/minimum-deletion-cost-to-avoid-repeating-letters/


Given a string s and an array of integers cost where cost[i] is the cost of deleting the character i in s.

Return the minimum cost of deletions such that there are no two identical letters next to each other.

Notice that you will delete the chosen characters at the same time, in other words, after deleting a character, the costs of deleting other characters will not change.



Example 1:

Input: s = "abaac", cost = [1,2,3,4,5]
Output: 3
Explanation: Delete the letter "a" with cost 3 to get "abac" (String without two identical letters next to each other).
Example 2:

Input: s = "abc", cost = [1,2,3]
Output: 0
Explanation: You don't need to delete any character because there are no identical letters next to each other.
Example 3:

Input: s = "aabaa", cost = [1,2,3,4,1]
Output: 2
Explanation: Delete the first and the last character, getting the string ("aba").


Constraints:

s.length == cost.length
1 <= s.length, cost.length <= 10^5
1 <= cost[i] <= 10^4
s contains only lowercase English letters.
*/

class Solution {
public:
    int minCost(string s, vector<int>& cost) {
        int ans=0, sum=0, c=cost[0], mx=cost[0], last=0;
        char cur=s[0];
        // remove all consecutive duplicates and leave one with the max cost
        for(int i=1;i<s.size();i++){
            if(s[i]==s[i-1]){
                c+=cost[i];
                mx=max(cost[i],mx);
                last=1;
            } else {
                ans+=c-mx;
                c=cost[i];
                mx=cost[i];
                last=0;
            }
        }
        // edge case
        if(last) ans+=c-mx;
        return ans;
    }
};

// same idea but shorter 
class Solution2 {
public:
    int minCost(string s, vector<int>& cost) {
        int res = 0, max_cost = 0, n = s.size();
        for (int i = 0; i < n; ++i) {
            if (i > 0 && s[i] != s[i - 1]) max_cost = 0;
            res += min(max_cost, cost[i]);
            max_cost = max(max_cost, cost[i]);
        }
        return res;
    }
};

There are other programming solutions in the following repositories below. Star and watch for timely updates!

GitHub logo wingkwong / competitive-programming

🌟 My CP Journey - This repository contains CP solutions (mostly written in C++) from different OJs and contest sites 🌟

Posted on by:

wingkwong profile

Wing-Kam

@wingkwong

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

Discussion

pic
Editor guide