Weekly Contest 325 | Take K of Each Character From Left and Right

*************************************************
Interview Experiences Playlists -

*********************************************************************

Please show support and subscribe if you find the content useful.

[tejaskatkade]

This solution is more intuitive rather than other techniques
Moral always start from basic 😅

[SDE-wqtl]

please add most optimal solutions for the problems, like sliding window in this case

[depression_plusplus]

I did using binary srch. Sliding window never occurred to me. I thought if you can remove from both sides sliding window will not be applicable and boy was I wrong.

In an interview setting, no way was I gonna think of sliding window

[soumikroy]

Java code
# Intuition
<!-- Describe your first thoughts on how to solve this problem. -->
n - max window size (which have the limit of count of sub-String [limit_A = totalA - k && limit_B = totalB - k && limit_C = totalC - k])..

# Approach
<!-- Describe your approach to solving the problem. -->
1) at first we need to calculate the hash value of every character..
2) if any of them is occuring < k directly return -1.
3) else we calculate limitCount of A, limitCount of B, limitCount of C.
4) then we maintain a windwow of max size which have the count of characters with in the limit.
5) when we get the max window at the end we return n - maxWindow.

# Complexity
- Time complexity:
<!-- Add your time complexity here, e.g. $$O(n)$$ -->
O:(N)
- Space complexity:
<!-- Add your space complexity here, e.g. $$O(n)$$ -->
O:(1)


# Code
```
class Solution {
public int takeCharacters(String s, int k) {
int hash[] = new int[3];
int n = s.length();

// we cal culculate the counts of a, b, c
for(char c : s.toCharArray()){
hash[c - 'a']++;
}

// if any of them is occurig < k directly return -1.
if(hash[0] < k || hash[1] < k || hash[2] < k){
return -1;
}

// calculate the max limit of occurrence a, b, c
int limitCountA = hash[0] - k, limitCountB = hash[1] - k, limitCountC = hash[2]-k;

// reset the hash values
Arrays.fill(hash, 0);

// here we maintain the max window which having the occurrence of a, b, c with in the limit of count.
int max = 0, left = 0;
for(int right = 0; right < n; right++){
hash[s.charAt(right) - 'a']++;
while(hash[0] > limitCountA || hash[1] > limitCountB || hash[2] > limitCountC){
hash[s.charAt(left) - 'a']--;
left++;
}
int window = right - left + 1;
max = Math.max(window, max);
}

return n - max;
}
}