Sliding window technique problem

what is a class and object in java

In our previous post, we learn about what sliding window technique is, In this post we are going to see some problem of sliding window technique.

We are going to solve 2 problem of leetcode, which is of medium level.

So, without wasting time, here is our question number 1.

Problem – 1 Grumpy Bookstore Owner || Sliding Window Problem

The bookstore owner has a store open for customers.length minutes.  Every minute, some number of customers (customers[i]) enter the store, and all those customers leave after the end of that minute.

On some minutes, the bookstore owner is grumpy.  If the bookstore owner is grumpy on the i-th minute, grumpy[i] = 1, otherwise grumpy[i] = 0.  When the bookstore owner is grumpy, the customers of that minute are not satisfied, otherwise they are satisfied.

The bookstore owner knows a secret technique to keep themselves not grumpy for X minutes straight, but can only use it once.

We need to find the total number of satisfied customer after technique is applied, such that we want maximum number of satisfied customer

Input: customers = [1,0,1,2,1,1,7,5], grumpy = [0,1,0,1,0,1,0,1], X = 3
Output: 16
Explanation: The bookstore owner keeps themselves not grumpy for the last 3 minutes. 
The maximum number of customers that can be satisfied = 1 + 1 + 1 + 1 + 7 + 5 = 16.

Hope, you go to leetcode and also give some time to problem.

Now, this is simple sliding window technique problem, Here is algo

  1. We know whenever grump value is 0, we are good to add it because owner is happy and this represent satisfied customer number in customer[]. So we add each customer[i] when grump[i] = 0;
  2. As owner is happy only for X minute by his technique, so to maximize the happy customer we need to find the max sum of length X in customer array when owner is upset i.e grumpy[i] = 1(same as max sum of subarray of size k)
  3. Now, add value obtained from point 1 and point 2 and return.

Here is code,

class Solution {
public:
    int maxSatisfied(vector<int>& customers, vector<int>& grumpy, int X) {
        
        
        int start = 0;
        int high = 0;
        int end = 0;
        int currSum = 0;
        int maxSum = 0;
         for(int end = 0; end < customers.size(); end++) {
            if (grumpy[end] == 1) {
                currSum += customers[end];
            }   
            if(end - start + 1 >= X) {
                high = max(high, currSum);
                if (grumpy[start] == 1) {
                    currSum -= customers[start];
                }
                start++;
            }
        }
        for(int i = 0;i<customers.size();i++)
        {
            if(grumpy[i] == 0)
                maxSum = maxSum+customers[i];
        }
        return maxSum+high;
    }
};

Problem 2(Medium) || Sliding window problem

You are given two strings s and t of the same length. You want to change s to t. Changing the i-th character of s to i-th character of t costs |s[i] - t[i]| that is, the absolute difference between the ASCII values of the characters.

You are also given an integer maxCost.

Return the maximum length of a substring of s that can be changed to be the same as the corresponding substring of twith a cost less than or equal to maxCost.

If there is no substring from s that can be changed to its corresponding substring from t, return 0.

Input: s = "abcd", t = "bcdf", maxCost = 3
Output: 3
Explanation: "abc" of s can change to "bcd". That costs 3, so the maximum length is 3.

This question is also easy one with help of sliding window technique, Hope you go to leetcode and try to submit.

Now, I am going to explain it.

  1. start from 0th index and calculate difference between both string character
  2. add difference in another variable(maxSum) and check if maxSum does not become greater than maxCost
  3. if maxSum is greater than maxCost then
diff = diff - abs(s[first]-t[first]);
first++;
tempLength--;
  • Repeat step 3 until maxSum become less than max Cost
  • also check for this in every step
if(finalLength<tempLength)
                finalLength= tempLength;

Here is complete code,

class Solution {
public:
    int equalSubstring(string s, string t, int maxCost) {
        int first = 0;
        int cont = 0;
        int diff = 0;
        int finalLength = 0;
        int tempLength = 0;
        int l = s.length();
        while(cont<l)
        {
            
            diff = diff+ abs(s[cont]-t[cont]);
            tempLength++;
            while(diff > maxCost)
            {
                diff = diff - abs(s[first]-t[first]);
                first++;
                tempLength--;
            }
            if(finalLength<tempLength)
                finalLength= tempLength;
            cont++;
            
            
        }
        while(diff > maxCost)
            {
                diff = diff - abs(s[first]-t[first]);
                first++;
                tempLength--;
            }
            if(finalLength<tempLength)
                finalLength= tempLength;
        return finalLength;
        
        
    }
};

Hope, you like this post and solution. Comment if any doubt exist.

Learn about vector here

Tagged :

Leave a Reply

Your email address will not be published. Required fields are marked *