# Easy explanation of Sliding window technique problem

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. This problem is famous in google search with name as “maximum satisfaction customer leetcode

We are going to solve 2 problems 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.

In 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 the satisfied customer after the technique is applied, such that we want the maximum number of a 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 `t`with 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 easily one with the help of a 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 the difference between both string character
2. add the difference in another variable(maxSum) and check if maxSum does not become greater than the max cost
3. if maxSum is greater than max cost 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. 