class Solution{
static long maximumSumSubarray(int k, ArrayList<Integer> arr,int n){
// code here
int s = 0;
int e = 0;
long sum = 0;
long ans = -1;
while(e<n){
if(e < k){
sum+=arr.get(e);
e++;
}
else if(e>=k){
ans = Math.max(ans,sum);
sum += arr.get(e) - arr.get(s);
s++;
e++;
}
}
ans = Math.max(ans,sum);
return ans;
}
}class Solution{
static long maximumSumSubarray(int k, ArrayList<Integer> arr,int n){
// code here
int s = 0, e = 0;
long sum = 0, max = 0;
while(e<n){
if(e<k){
sum+=arr.get(e);
e++;
}
else {
max = Math.max(sum, max);
sum = sum - arr.get(s) + arr.get(e);
s++; e++;
}
}
max = Math.max(sum,max);
return max;
}
}class Compute {
public long[] printFirstNegativeInteger(long arr[], int n, int k)
{
long ans[]=new long[n-k+1]; // size of ans[] = number of possible windows
int s=0,e=k-1;
int j=0;
boolean flag=false;
while(e<n){
for(int i=s;i<=e;i++){
flag=false;
if(arr[i]<0){
ans[j++]=arr[i]; flag=true;
break;
}
}
if(!flag) j++; // this will automaticaly add 0
s++;
e++;
}
return ans;
}
}- Step 1 : Create a Initial Answer means for 1st Window
- Step 2 : Make everything ready for next coming window
- Step 3 : Inside loop calculate ans for that window than s++; e++.
class Compute {
public long[] printFirstNegativeInteger(long arr[], int n, int k)
{
Queue<Long> q=new LinkedList<>();
int s = 0;
int e = 0;
long[] ans = new long[n-k+1]; int idx = 0;
while(e<n){
if(e<k){
if(arr[e] < 0) q.add(arr[e]);
e++;
}
else if(e>=k){
if(!q.isEmpty()) ans[idx] = q.peek();
idx++;
if(!q.isEmpty() && arr[s] == q.peek()){
q.remove();
}
s++;
if(arr[e] < 0) q.add(arr[e]);
e++;
}
}
if(!q.isEmpty()) ans[idx] = q.peek();
return ans;
}
}- HM which u make from pat think it as a AvailabilityList for window. i.e., in a window How Many distictcharacter can accomodate.
- say like in a window 3a's 1b can live. or else say in a window a has 3bed b has 1bed
- count denotes no.OfDistinct Character which can accomodate i.e count of Distinctcharacter who can stay in window
- so whenever u add a charcter in window then u occupy 1bed of that character if available so u do -1 from that character's beds.
- if beds of that character turnsout to be 0 after -1 then count--;
- let's say u r going to remove one character from that window that means bed of that character will increase by +1.
- if bed of that character is already 0 then u do count++
class Solution {
int search(String pat, String txt) {
// code here
HashMap<Character, Integer> hm=new HashMap<>();
for(char c: pat.toCharArray()){
if(!hm.containsKey(c)){
hm.put(c,1);
}
else {
hm.put(c, hm.get(c)+1);
}
}
int count = hm.size();
// HM made - here if -ve value says extra & +ve value says deficient
// if u look HM with txt then value says "Window k pass # ki kami hai orelse meh = hoejata"
char ch[] = txt.toCharArray();
int s = 0;
int e = 0;
int k = pat.length();
int ans = 0;
int n = ch.length;
while(e<n){
if(e<k){
if(hm.containsKey(ch[e])){
hm.put(ch[e], hm.get(ch[e])-1);
if(hm.get(ch[e]) == 0) count--;
}
e++;
}
else {
if(count == 0) ans++;
// start slide means if someone going then +1
if(hm.containsKey(ch[s])){
if(hm.get(ch[s]) == 0) count++;
hm.put(ch[s], hm.get(ch[s]) + 1);
}
s++;
// end slide
if(hm.containsKey(ch[e])){
hm.put(ch[e], hm.get(ch[e])-1);
if(hm.get(ch[e]) == 0) count--;
}
e++;
}
}
if(count==0) ans++;
return ans;
}
}TCs - [13, 7, 12, 6, 5, 3, 6, 7]
class Solution {
public int[] maxSlidingWindow(int[] nums, int k) {
int n = nums.length;
int ans[] = new int[n-k+1]; int idx = 0;
Deque<Integer> dq=new LinkedList<>();
int s = 0;
int e = 0;
while(e<n){
if(e<k){
if(dq.isEmpty()) dq.add(nums[e]);
else {
while(!dq.isEmpty() && nums[e] > dq.peekLast()) dq.removeLast();
dq.add(nums[e]);
}
e++;
}
else{
ans[idx++] = dq.peek();
// start slide
if(!dq.isEmpty() && dq.peek() == nums[s]) dq.removeFirst();
s++;
// end slide
while(!dq.isEmpty() && nums[e] > dq.peekLast()) dq.removeLast();
dq.add(nums[e]);
e++;
}
}
ans[idx] = dq.peek();
return ans;
}
}Note : This will work only for +VE Integer in array
A. No. Because let's say in the given array [4,1,1,1,2,3,5] when we found the sum within the window to be greater than the desired value 5 (i=0, j=2 -> [4,1,1]), we started reducing the size of the window by doing i++. Here we assumed that once the sum of elements within the window becomes greater than 5 then increasing the window size will just add to the sum and hence we will not attain the sum 5 again. This is true when all the element are positive and hence reducing the window size by doing i++ makes sense. But this might not be true if array also contains negative numbers. Consider the array [4,1,1,-2,1,5], here we would have found the sum to be greater than 5 for i=0, j=2 and if we would have now started reducing the window size by doing i++, we would have missed the potential subarray (i=0, j=4). In short, the discussed approach will not work with array having negative numbers.
private static int lsa(int arr[],int n, int k) {
int max=0,sum=0;
int s=0,e=0;
while(e<n) {
sum+=arr[e];
while(sum>k) {
sum-=arr[s];
s++;
}
if(sum==k) {
max=Math.max(max,e-s+1);
}
e++;
}
return max;
}class Solution{
// Function for finding maximum and value pair
public static int lenOfLongSubarr (int arr[], int n, int k) {
//Complete the function
HashMap<Integer,Integer> hm=new HashMap<>();
int sum=0,max=0;
hm.put(0,-1);
for(int i=0;i<n;i++){
sum+=arr[i];
if(!hm.containsKey(sum)) hm.put(sum,i); // we may get the sum which is already present in HM so to always get the longest subarray we are not modifying
if(hm.containsKey(sum-k)){
max=Math.max(max,i-hm.get(sum-k));
}
}
return max;
}
}
class Solution {
public int longestkSubstr(String str, int k) {
// code here
int n=str.length();
int s=0,e=0;
int uc=0,ans=-1;
HashMap<Character,Integer> hm=new HashMap<>();
while(e<n){
char ch=str.charAt(e);
hm.put(ch,hm.getOrDefault(ch,0)+1);
uc=hm.size();
while(uc>k){
ch=str.charAt(s);
hm.put(ch,hm.get(ch)-1);
if(hm.get(ch)==0) hm.remove(ch);
uc=hm.size();
s++;
}
if(uc==k){
ans=Math.max(ans,e-s+1);
}
e++;
}
return ans;
}
}or
class Solution {
public int longestkSubstr(String str, int k) {
// code here
int s = 0, e = 0, n = str.length();
int ans = -1, l=0; // length of substring
int uc = 0; // unique character
HashMap<Character, Integer> hm=new HashMap<>();
while(e<n){
char c = str.charAt(e);
hm.put(c, hm.getOrDefault(c,0)+1);
uc = hm.size(); l++;
if(uc > k){
char sc = str.charAt(s);
hm.put(sc, hm.get(sc)-1); l--;
if(hm.get(sc)==0) hm.remove(sc);
s++;
}
else if(uc==k){
ans = Math.max(ans,l);
}
e++;
}
return ans;
}
}class Solution {
public int lengthOfLongestSubstring(String str) {
int n=str.length();
int s=0,e=0;
int uc=0,ans=0;
HashMap<Character,Integer> hm=new HashMap<>();
while(e<n){
char ch=str.charAt(e);
hm.put(ch,hm.getOrDefault(ch,0)+1);
uc=hm.size();
while(uc<(e-s+1)){
ch=str.charAt(s);
hm.put(ch,hm.get(ch)-1);
if(hm.get(ch)==0) hm.remove(ch);
uc=hm.size();
s++;
}
if(uc==(e-s+1)){
ans=Math.max(ans,e-s+1);
}
e++;
}
return ans;
}
}or
class Solution {
public int lengthOfLongestSubstring(String str) {
int s = 0, e = 0, n = str.length();
int ans = 0, l=0; // length of substring
int uc = 0; // unique character
HashMap<Character, Integer> hm=new HashMap<>();
while(e<n){
char c = str.charAt(e);
hm.put(c, hm.getOrDefault(c,0)+1);
uc = hm.size(); l++;
if(l > uc){
char sc = str.charAt(s);
hm.put(sc, hm.get(sc)-1); l--;
if(hm.get(sc)==0) hm.remove(sc);
s++;
}
else if(l==uc){
ans = Math.max(ans,l);
}
e++;
}
return ans;
}
}
public static int countSubstring(String str, int k){
HashMap<Character> hm = new HashMap<>();
int s = 0;
int e = 0;
int ans = 0;
while(e<n){
char ch = str.charAt(e);
hm.put(ch, hm.getOrDefault(ch,0)+1);
int uc = hm.size();
while(uc > k){
char rc = str.charAt(s);
hm.put(rc, hm.get(rc) - 1);
if(hm.get(rc) == 0) hm.remove(rc);
uc = hm.size();
s++;
}
ans+= e-s+1;
e++;
}
return ans;
}- str = "bbaacdedf" k = 2 output = 34
Hint : As soon as your window hit the condition i.e., uniqueCharacter == k then addition of any character will just increase it length only and will give rise to new substring only which will be valid bcz uniqueCharacter will increase only.
public static int countSubstring(String str, int k){
int n = str.length();
int s = 0;
int e = 0;
HashMap<Character, Integer> hm=new HashMap<>();
int uc = 0;
int ans = 0;
while(e<n){
char ch = str.charAt(e);
hm.put(ch, hm.getOrDefault(ch, 0) + 1);
uc = hm.size();
while(uc == k){
ans+=n-e;
char rc = str.charAt(s);
hm.put(rc, hm.get(rc) - 1);
if(hm.get(rc) == 0) hm.remove(rc);
uc = hm.size();
s++;
}
e++;
}
return ans;
}
class Solution {
public int subarraysWithKDistinct(int[] nums, int k) {
return atmostK(nums,k) - atmostK(nums,k-1);
}
private int atmostK(int arr[], int k){
int n = arr.length;
HashMap<Integer, Integer> hm=new HashMap<>();
int s = 0;
int e = 0;
int uc = 0;
int ans = 0;
while(e < n){
int ele = arr[e];
hm.put(ele, hm.getOrDefault(ele, 0) + 1);
uc = hm.size();
while(uc > k){
int rc = arr[s];
hm.put(rc, hm.get(rc) - 1);
if(hm.get(rc) == 0) hm.remove(rc);
uc = hm.size();
s++;
}
ans+=e-s+1;
e++;
}
return ans;
}
}public int lengthOfLongestSubstringTwoDistinct(String str) {
// Write your code here
int n=str.length();
int s=0,e=0;
int uc=0,ans=0;
HashMap<Character,Integer> hm=new HashMap<>();
while(e<n){
char ch=str.charAt(e);
hm.put(ch,hm.getOrDefault(ch,0)+1);
uc=hm.size();
while(uc>2){
ch=str.charAt(s);
hm.put(ch,hm.get(ch)-1);
if(hm.get(ch)==0) hm.remove(ch);
uc=hm.size();
s++;
}
if(uc==2 || uc<2){
ans=Math.max(ans,e-s+1);
}
e++;
}
return ans;
}class Solution {
public String minWindow(String str, String t) {
// Step 1 Make HM for String t
HashMap<Character,Integer> hm=new HashMap<>();
for(int i=0;i<t.length();i++){
char ch=t.charAt(i);
hm.put(ch,hm.getOrDefault(ch,0)+1);
}
int count=hm.size();
// Step 2 Variable Sliding window Starts
int s=0,e=0;
int ans=Integer.MAX_VALUE,as=0,ae=0;
int n=str.length();
while(e<n){
char ch=str.charAt(e);
if(hm.containsKey(ch)){
hm.put(ch,hm.get(ch)-1);
if(hm.get(ch)==0) count--;
}
while(count==0){
if((e-s+1)<ans){
ans=e-s+1;
as=s;
ae=e;
}
ch=str.charAt(s);
if(hm.containsKey(ch)){
hm.put(ch,hm.get(ch)+1);
if(hm.get(ch)>0) count++;
}
s++;
}
e++;
}
if(as==ae && s==0) return "";
return str.substring(as,ae+1);
}
}