Weekly Contest 282 LeetCode Solution

Problem 1 – Counting Words With a Given Prefix Leetcode Solution

You are given an array of strings words and a string pref.

Return the number of strings in words that contain pref as a prefix.

prefix of a string s is any leading contiguous substring of s.

Example 1:

Input: words = ["pay","attention","practice","attend"], pref = "at"
Output: 2
Explanation: The 2 strings that contain "at" as a prefix are: "attention" and "attend".

Example 2:

Input: words = ["leetcode","win","loops","success"], pref = "code"
Output: 0
Explanation: There are no strings that contain "code" as a prefix.

Constraints:

  • 1 <= words.length <= 100
  • 1 <= words[i].length, pref.length <= 100
  • words[i] and pref consist of lowercase English letters.

Counting Words With a Given Prefix Leetcode Solution in C++

// The easiest solution to this problem is:
// Step 1: Calculate length of "pref"
// Step 2: find substring of "words" from 0 to length of "pref"
// if both match increment count by 1;



class Solution {
public:
    int prefixCount(vector<string>& words, string pref) {
        
        int count=0;
        int preflen=pref.size();        //step 1
        
        for(auto i:words){
            if(i.substr(0,preflen) == pref)     //step 2
                count++;                        //if both matches then increment count by 1
            
        }
        return count;   //return count
        
    }
};

Counting Words With a Given Prefix Leetcode Solution in Java

    public int prefixCount(String[] words, String pref) {
        return (int)Stream.of(words).filter(w -> w.startsWith(pref)).count();
    }

Counting Words With a Given Prefix Leetcode Solution in Python 3

    def prefixCount(self, words: List[str], pref: str) -> int:
        return sum(w.startswith(pref) for w in words)

Counting Words With a Given Prefix Leetcode Solution in Python

def prefixCount(self, words: List[str], pref: str) -> int:
	return sum([word.startswith(pref) for word in words])

Counting Words With a Given Prefix Leetcode Solution in JavaScript

var prefixCount = function(words, pref) {
    return words.filter(word => word.slice(0, pref.length) === pref).length;
};

Problem 2 – Minimum Number of Steps to Make Two Strings Anagram II Leetcode Solution

You are given two strings s and t. In one step, you can append any character to either s or t.

Return the minimum number of steps to make s and t anagrams of each other.

An anagram of a string is a string that contains the same characters with a different (or the same) ordering.

Example 1:

Input: s = "leetcode", t = "coats"
Output: 7
Explanation: 
- In 2 steps, we can append the letters in "as" onto s = "leetcode", forming s = "leetcodeas".
- In 5 steps, we can append the letters in "leede" onto t = "coats", forming t = "coatsleede".
"leetcodeas" and "coatsleede" are now anagrams of each other.
We used a total of 2 + 5 = 7 steps.
It can be shown that there is no way to make them anagrams of each other with less than 7 steps.

Example 2:

Input: s = "night", t = "thing"
Output: 0
Explanation: The given strings are already anagrams of each other. Thus, we do not need any further steps.

Constraints:

  • 1 <= s.length, t.length <= 2 * 105
  • s and t consist of lowercase English letters.

Minimum Number of Steps to Make Two Strings Anagram II Leetcode Solution in C++

class Solution {
public:
    int minSteps(string s, string t) {
        
        int count=0;
        //take an array of 26 size to store frequency of alphabets
        vector<int> arr(26,0);
        
        
        //increment the frequency of character by 1 in the array
        for(auto i:s)
            arr[i-'a']++;
        
        //decrement the frequency of character by 1 in the array
        for(auto i:t)
            arr[i-'a']--;
        
        // Now the array will only store the frequency of characters that are different
        for(auto i:arr)
            count+=abs(i);
        
        return count;
        
        
        
    }
};

Minimum Number of Steps to Make Two Strings Anagram II Leetcode Solution in Python 3

class Solution:
    def minSteps(self, s: str, t: str) -> int:
        fs, ft = Counter(s), Counter(t)
        return sum((fs-ft).values()) + sum((ft-fs).values())

Minimum Number of Steps to Make Two Strings Anagram II Leetcode Solution in Java

class Solution {
    public int minSteps(String s, String t) {
        int cnt[] = new int[26], ans = 0;
        for (char c : s.toCharArray()) cnt[c - 'a']++;
        for (char c : t.toCharArray()) cnt[c - 'a']--;
        for (int n : cnt) ans += Math.abs(n);
        return ans;
    }
}

Minimum Number of Steps to Make Two Strings Anagram II Leetcode Solution in Swift

class Solution {
  func minSteps(_ s: String, _ t: String) -> Int {
    var counter = [Character: Int]()
    for c in s {
      counter[c, default: 0] += 1 
    }
    
    for c in t {
      counter[c, default: 0] -= 1 
    }
    
    var res = 0 
    for diff in counter.values {
      res += abs(diff)
    }
    
    return res
  }
} 

Minimum Number of Steps to Make Two Strings Anagram II Leetcode Solution in Python

class Solution:
    def minSteps(self, s: str, t: str) -> int:
        a=Counter(s)
        b=Counter(t)
        c=(a-b)+(b-a)
        
        count=0
        for i in c:
            count+=c[i]
        return count

Problem 3 – Minimum Time to Complete Trips Leetcode Solution

You are given an array time where time[i] denotes the time taken by the ith bus to complete one trip.

Each bus can make multiple trips successively; that is, the next trip can start immediately after completing the current trip. Also, each bus operates independently; that is, the trips of one bus do not influence the trips of any other bus.

You are also given an integer totalTrips, which denotes the number of trips all buses should make in total. Return the minimum time required for all buses to complete at least totalTrips trips.

Example 1:

Input: time = [1,2,3], totalTrips = 5
Output: 3
Explanation:
- At time t = 1, the number of trips completed by each bus are [1,0,0]. 
  The total number of trips completed is 1 + 0 + 0 = 1.
- At time t = 2, the number of trips completed by each bus are [2,1,0]. 
  The total number of trips completed is 2 + 1 + 0 = 3.
- At time t = 3, the number of trips completed by each bus are [3,1,1]. 
  The total number of trips completed is 3 + 1 + 1 = 5.
So the minimum time needed for all buses to complete at least 5 trips is 3.

Example 2:

Input: time = [2], totalTrips = 1
Output: 2
Explanation:
There is only one bus, and it will complete its first trip at t = 2.
So the minimum time needed to complete 1 trip is 2.

Constraints:

  • 1 <= time.length <= 105
  • 1 <= time[i], totalTrips <= 107

Minimum Time to Complete Trips Leetcode Solution in Java

    public long minimumTime(int[] time, int totalTrips) {
        long lo = 0, hi = 100_000_000_000_000L;
        while (lo < hi) {
            long need = lo + (hi - lo) / 2;
            long trips = 0;
            for (int t : time) {
                trips += need / t;
            }
            if (trips < totalTrips) {
                lo = need + 1;
            }else {
                hi = need;
            }
        }
        return lo;
    }

Minimum Time to Complete Trips Leetcode Solution in Python 3

    def minimumTime(self, time: List[int], totalTrips: int) -> int:
        lo, hi = 0, 10 ** 14
        while lo < hi:
            need = lo + (hi - lo) // 2
            trips = sum(need // t for t in time)
            if trips < totalTrips:
                lo = need + 1
            else:
                hi = need
        return lo

Minimum Time to Complete Trips Leetcode Solution in C++

class Solution {
public:
    long long minimumTime(vector<int>& time, int totalTrips) {
        long long anstillnow=-1;
        
        long long left=1, right= 100000000000001;          //can also write this as 1+1e14
		
        while(left<=right){
            long long mid= left+ (right-left)/2;   // find mid point like this to avoid overflow
            long long curr_trips=0;
            for(int t: time){
                curr_trips+= mid/t;
            }
            
            if(curr_trips>=totalTrips){ 
                anstillnow=mid;
                right=mid-1;
            }
            
            else{
                left=mid+1;
            }
        }
        
        return anstillnow;
    }
};

Minimum Time to Complete Trips Leetcode Solution in Python

class Solution(object):
    def minimumTime(self, time, totalTrips):
        anstillnow=-1;
        left=1;
        right= 100000000000001;
        
        while(left<=right):
            mid= left+ (right-left)/2      #find mid point like this to avoid overflow
            
            curr_trips=0;
            
            for t in time:
                curr_trips+= mid/t
            
            if(curr_trips>=totalTrips):
                anstillnow=mid
                right=mid-1
            
            else:
                left=mid+1

        return anstillnow

Minimum Time to Complete Trips Leetcode Solution in Swift

class Solution {
  func minimumTime(_ time: [Int], _ totalTrips: Int) -> Int {
    func isValid(_ t: Int) -> Bool {
      var numberOfTrips = 0
      for busTime in time {
        numberOfTrips += (t / busTime)
		
		// as soon as we've completed at least `totalTrips`, t is valid candidate
		if numberOfTrips >= totalTrips {
		   return true
		}
      }
      
      return false
    }
    
    let longestTime = time.max() ?? 0    
    var res = 0
    var (low, high) = (1, longestTime * totalTrips)
    while low <= high {
      let mid = low + (high - low) / 2
      if isValid(mid) {
        res = mid
        high = mid - 1 
      } else {
        low = mid + 1
      }
    }
    
    return res
  }
}

Problem 4 – Minimum Time to Finish the Race Leetcode Solution

You are given a 0-indexed 2D integer array tires where tires[i] = [fi, ri] indicates that the ith tire can finish its xth successive lap in fi * ri(x-1) seconds.

  • For example, if fi = 3 and ri = 2, then the tire would finish its 1st lap in 3 seconds, its 2nd lap in 3 * 2 = 6 seconds, its 3rd lap in 3 * 22 = 12 seconds, etc.

You are also given an integer changeTime and an integer numLaps.

The race consists of numLaps laps and you may start the race with any tire. You have an unlimited supply of each tire and after every lap, you may change to any given tire (including the current tire type) if you wait changeTime seconds.

Return the minimum time to finish the race.

Example 1:

Input: tires = [[2,3],[3,4]], changeTime = 5, numLaps = 4
Output: 21
Explanation: 
Lap 1: Start with tire 0 and finish the lap in 2 seconds.
Lap 2: Continue with tire 0 and finish the lap in 2 * 3 = 6 seconds.
Lap 3: Change tires to a new tire 0 for 5 seconds and then finish the lap in another 2 seconds.
Lap 4: Continue with tire 0 and finish the lap in 2 * 3 = 6 seconds.
Total time = 2 + 6 + 5 + 2 + 6 = 21 seconds.
The minimum time to complete the race is 21 seconds.

Example 2:

Input: tires = [[1,10],[2,2],[3,4]], changeTime = 6, numLaps = 5
Output: 25
Explanation: 
Lap 1: Start with tire 1 and finish the lap in 2 seconds.
Lap 2: Continue with tire 1 and finish the lap in 2 * 2 = 4 seconds.
Lap 3: Change tires to a new tire 1 for 6 seconds and then finish the lap in another 2 seconds.
Lap 4: Continue with tire 1 and finish the lap in 2 * 2 = 4 seconds.
Lap 5: Change tires to tire 0 for 6 seconds then finish the lap in another 1 second.
Total time = 2 + 4 + 6 + 2 + 4 + 6 + 1 = 25 seconds.
The minimum time to complete the race is 25 seconds. 

Constraints:

  • 1 <= tires.length <= 105
  • tires[i].length == 2
  • 1 <= fi, changeTime <= 105
  • 2 <= ri <= 105
  • 1 <= numLaps <= 1000

Minimum Time to Finish the Race Leetcode Solution in C++

class Solution {
public:
    int minimumFinishTime(vector<vector<int>>& tires, int changeTime, int numLaps) {
        int n = tires.size();
        // to handle the cases where numLaps is small
		// without_change[i][j]: the total time to run j laps consecutively with tire i
        vector<vector<int>> without_change(n, vector<int>(20, 2e9));
        for (int i = 0; i < n; i++) {
            without_change[i][1] = tires[i][0];
            for (int j = 2; j < 20; j++) {
                if ((long long)without_change[i][j-1] * tires[i][1] >= 2e9)
                    break;
                without_change[i][j] = without_change[i][j-1] * tires[i][1];
            }
            // since we define it as the total time, rather than just the time for the j-th lap
			// we have to make it prefix sum
            for (int j = 2; j < 20; j++) {
                if ((long long)without_change[i][j-1] + without_change[i][j] >= 2e9)
                    break;
                without_change[i][j] += without_change[i][j-1];
            }
        }
        
		// dp[x]: the minimum time to finish x laps
        vector<int> dp(numLaps+1, 2e9);
        for (int i = 0; i < n; i++) {
            dp[1] = min(dp[1], tires[i][0]);
        }
        for (int x = 1; x <= numLaps; x++) {
            if (x < 20) {
				// x is small enough, so an optimal solution might never changes tires!
                for (int i = 0; i < n; i++) {
                    dp[x] = min(dp[x], without_change[i][x]);
                }
            }
            for (int j = x-1; j > 0 && j >= x-18; j--) {
                dp[x] = min(dp[x], dp[j] + changeTime + dp[x-j]);
            }
        }
        
        return dp[numLaps];
    }
};

Minimum Time to Finish the Race Leetcode Solution in Python

class Solution:
    def minimumFinishTime(self, tires: List[List[int]], changeTime: int, numLaps: int) -> int:
        
        optimal = [math.inf]*(numLaps+1)
        for a,b in tires:
            curCost = a
            curTire = 1
            totalCost = a
            while curTire<=16 and curTire<(numLaps+1):
                optimal[curTire] = min(optimal[curTire], totalCost)
                curCost = curCost * b
                totalCost = curCost+totalCost
                curTire+=1

        for i in range(1,numLaps+1):
            for j in range(i-1):
                #if we switch tire at jth point 
                optimal[i] = min(optimal[i],changeTime + optimal[j+1] + optimal[i-(j+1)])
                

        return optimal[-1]
		```

Minimum Time to Finish the Race Leetcode Solution in Java

class Solution {
    public int minimumFinishTime(int[][] tires, int changeTime, int numLaps) {
        int[] minTime = new int[numLaps + 1];
        Arrays.fill(minTime, Integer.MAX_VALUE);
        for (int[] tire : tires) {
            checkMinTime(tire, minTime, changeTime, numLaps);
        }
        for (int i = 2; i <= numLaps; i++) {
            for (int j = 1; j < i; j++) {
                int remain = i % j;
                int currMin;
				// Greedy, in order to get the minimal runtime, we should repeat the same loop as much as possible.
                if (remain != 0) {
                    currMin = (i / j) * (minTime[j] + changeTime) + minTime[remain];
                } else {
					// The last changeTime is not required if remain is 0
                    currMin = (i / j) * (minTime[j] + changeTime) - changeTime; 
                }
                minTime[i] = Math.min(minTime[i], currMin);
            }
        }

        return minTime[numLaps];
    }
    
    private void checkMinTime(int[] tire, int[] minTime, int changeTime, int numLaps) {
        int base = tire[0];
        int lap = 1;
        int curr = base;
        minTime[lap] = Math.min(minTime[lap], curr);
        int sum = base;
		// Greedy, if changeTime + base is smaller, the minimal runtime for the next lap
		// will not be better than minTime[lap - 1] + changeTime + minTime[1] 
        while (curr * tire[1] - base <= changeTime && lap++ < numLaps) {
            curr *= tire[1];
            sum += curr;
            minTime[lap] = Math.min(minTime[lap], sum);
        }
    }
}

Minimum Time to Finish the Race Leetcode Solution in JavaScript

var minimumFinishTime = function(tires, changeTime, numLaps) {  
    const n = tires.length
    const smallestTire = Math.min(...tires.map(t => t[1]))
    const maxSameTire = Math.floor(Math.log(changeTime) / Math.log(smallestTire)) + 1
    const sameTireLast = Array(n).fill(0)
	
	// DP array tracking what is the min cost to complete lap i using same tire
    const sameTire = Array(maxSameTire + 1).fill(Infinity)
    for (let lap = 1; lap <= maxSameTire; lap++) {
        tires.forEach((tire, i) => {
            sameTireLast[i] += tire[0] * tire[1] ** (lap - 1)
            sameTire[lap] = Math.min(sameTire[lap], sameTireLast[i])
        })
    }
    
    const dp = Array(numLaps + 1).fill(Infinity)
    for (let i = 1; i < numLaps + 1; i++) {
        if (i <= maxSameTire) dp[i] = sameTire[i]
		// at each lap, we can either use the same tire up to this lap (sameTire[i])
		// or a combination of 2 different best times, 
		// eg lap 6: use best time from lap 3 + lap 3
		// or from lap 4 + lap 2
		// or lap 5 + lap 1
        for (let j = 1; j < i / 2 + 1; j++) {
            dp[i] = Math.min(dp[i], dp[i-j] + changeTime + dp[j])
        }
    }
    return dp[numLaps]
};
Weekly Contest 282 LeetCode Solution Review:

In our experience, we suggest you solve this Weekly Contest 282 LeetCode Solution and gain some new skills from Professionals completely free and we assure you will be worth it.

If you are stuck anywhere between any coding problem, just visit Queslers to get the Weekly Contest 282 LeetCode Solution

Find on LeetCode

Conclusion:

I hope this Weekly Contest 282 LeetCode Solution would be useful for you to learn something new from this problem. If it helped you then don’t forget to bookmark our site for more Coding Solutions.

This Problem is intended for audiences of all experiences who are interested in learning about Data Science in a business context; there are no prerequisites.

Keep Learning!

More Coding Solutions >>

LeetCode Solutions

Hacker Rank Solutions

CodeChef Solutions

Leave a Reply

Your email address will not be published.