SUMMARY : VERY HARD

1. Problem Easy

Wael always makes problems that are hard to solve, so he decided to create an easy problem, or is it really an easy problem? He invited his dear friend, Kaito to dinner and asked him to solve the problem he just created, Wael told Kaito:

You will be given a sequence of small Latin letters S. For each unique letter in the sequence, you have to delete all the occurrences of this letter except for only one occurrence. In the other words, if the occurrence of the letter excepts for only one occurrence, IN other words, if the letter “C” appear X times in the sequence, you have to delete (X-1) occurrences of the letter and leave only one however, if the letter “C” appears only once, then you can’t delete it.

Given the sequence S, your task is to find the lexicographically maximum resulting sequence and print the Hash value of the resulting sequence. You need to use Hash Function given below to print the Hash Function given below to print the hash value of the resulting sequence:

 int get_hash(string Result)
 {
   long long p = 31, res = 0;
   long long mod 1000000007;
   for (int i = 0; i < (int)Result.length(); i++)
   {
       res += ((Result[i] - 'a' + 1) * (p % mod)) % mod;
       res %= mod;
       p *= 31;
       p %= mod;
   }
   return res % mod;
 }

Note: A string a of length N is lexicographically less than a string b of length M, if:
• There is an index I (1<= i <=min(N, M)) such that the first i=1 characters of string a and b the same, the ith character of the string a is less than ith character of the string b.
• OR the first min(N, M) characters in the string a and b are the same and n<m.

INPUT
The first line contains the string s

SAMPLE INPUT, SAMPLE OUTPUT , EXPLANATION
abacaba , 3186 , Delete the following indexes : {1, 2,3,5} The resulting sequence [cba] is the lexicographically maximum possible
aezakmi , 3699255699 , Delete the first letter and the resulting sequence [ezakmi] is optimal.
convexhull , 740262355 , Delete the last letter and the resulting sequence [convexhul] is optimal.

ans : https://leetcode.com/problems/remove-duplicate-letters/submissions/
just a need to find maximum rather than smallest

2. Problem Medium

You are given N integers where the ith integer is denoted by A[ i ] such that 1 <= i <= N . You are also given integer M and another integer C.
Your task is to find the count of subarrays of A size M, where the difference between the largest value and the smallest value in the subarray is at-most C.
This means you need to find the of all indices i such that 1 <= i <= N – M+1 plus satisfies the relationship defined below:

Max{A[i],….A[i+M-1]} – Min{A[i],….A[i+M-1]} <= C

INPUT FORMAT
The first line contains an integer N, denoting the count of integers given.
The next line contains an integer M, denoting the required size of subarrays
The next line contains an integer C, denoting the upper bound on the difference between the biggest and the smallest value in each subarray
Each line I of the N subsequent lines (where 0 <= i <= N) contains an integers describing Ai

CONSTRAINTS
1 <= N <= 10^6
1<= M <=10^3
1<= C <= 10^3
1<= A[i] <=10^6

Sample Input , Sample Output , Explanation
3 2 1 1 4 2 , 0 , Here the subarray of size 2 (M=2) formed from index 2 until 3 (A[2]..A[3]) is valid since biggest value is 1 and the smallest value is also 1 so 1-1 <= C <= 0 since C=0. The other valid subarray is from index 6 to 7
(A[6]…A[7])
7 2 0 0 1 1 3 2 2 2 , Here we have
one valid subarray only.
From index 5 until 10
with size M=010-08-2021

My Approach : FULLY ACCEPTED

Basic : Traverse whole array and find min and max of each window and compare their difference with C.
O(n^2) approach and input is 10^6 so it will give TLE.

Efficient O(n)

  int solve(vector<int> arr, int N, int M, int C) 
{
vector<int> submin = get_subminarr(Arr, N, M);
vector<int> submax = get_submaxarr(Arr, N, M);

int minn = submax[0] - submin[0];
int n = submax.size();
int cnt = 0;

for (int i = 0; i < n; i++)
{
    int dif = submax[i] - submin[i];
    if (dif <= C)
        cnt++;
}
return cnt; 
}

vector<int> get_submaxarr(vector<int> arr, int n, int y)
 {
   int j = 0;
stack<int> stk;
vector<int> maxarr(n);
stk.push(0);
for (int i = 1; i < n; i++)
{
	while (stk.empty() == false and arr[i] > arr[stk.top()])
    {
        maxarr[stk.top()] = i - 1;
        stk.pop();
    }
    stk.push(i);
}

while (!stk.empty())
{
    maxarr[stk.top()] = n - 1;
    stk.pop();
}
vector<int> submax;

for (int i = 0; i <= n - y; i++)
{
    while (maxarr[j] < i + y - 1 or j < i)
    {
        j++;
    }

    submax.push_back(arr[j]);
}
return submax; 
} 
vector<int> get_subminarr(vector<int> arr, int n, int y)
{
int j = 0;
vector<int> minarr(n);
stk.push(0);

for (int i = 1; i < n; i++)
{
    while (stk.empty() == false and arr[i] < arr[stk.top()])
    {
        minarr[stk.top()] = i;
        stk.pop();
    }
    stk.push(i);
}

while (!stk.empty())
{
    minarr[stk.top()] = n;
    stk.pop();
}

vector<int> submin;
for (int i = 0; i <= n - y; i++)
{
    while (minarr[j] <= i + y - 1 or j < i)
    {
        j++;
    }
    submin.push_back(arr[j]);
}
return submin;
}

Soon UPDATING 3rd HARD
If its help full, upvote