22. Sliding Window & 2 pointer

Conditions for Sliding Window-

1. Monotonic condition
2. Subarray sum problems with positive numbers
3. Window validity behave predictably upon expand / shrink

If, above conditions gets violated in a subarray problem, we go with below methods-
1. prefix sum + hashmap
2. DP
3. Binary Search

---------------------------------------------------------------------------------------------------------------------------

4 Patterns in Sliding Window-
(striver)

1. Fix window-

❄️ Build 1st window of size k => slide window (L++, R++) => update state =>update ans
-----------------------------------------------------
2. Variable window-1
- (Find longest subarray satisfying a condition )
- for each R, smallest index L, which keeps window valid, is chosen.

❄️expand R => while window invalid: (shrink L) => now, update answer
---------------------------------------------------

3. Variable window-2
- (Count subarrays satisfying a condition )
- (current window invalid => all larger windows are invalid)
- (current window valid => all smaller windows are valid)
- for each R, smallest L which keeps window valid is chosen

❄️expand R => while window invalid: (shrink L) => now, update cnt += (R-L+1)
------------------------------------------------

4. Shortest window⭐
- (find smallest subarray with a given condition )
- (current window invalid => all larger windows are invalid)
- expand till current window is invalid => once valid, now shrink it to make it as small as possible => when it becomes invalid, stop shrinking => continue expanding

❄️ expand R => while window is valid (update ans & shrink L ) => repeat
---------------------------------------------------------------------------------------------------------------------------

4 Patterns in Sliding Window-
(me)

1. Fixed window
2. At most K bad elements
3. Exactly K elements (via, at most K - at most K-1)
4. Shortest Valid window
--------------------------------------------------------------------------------------------------------------------------

1. Find length of longest substring-
 (with all distinct characters)

----------------------------

Brute- time: O(n^2)   space: O(n)

go through all substrings and check if they contain unique characters or not using a map

------------------------------------------------------

Optimal- time: O(n)  space: O(n)

use sliding window with hashmap storing character, index of appearance

1. if character at j-th index already appeared in current window, then shift i accordingly

2. update the map with current character and its index of appearance
3. update answer with max length of substring
4. move j

----------------------------------------------------------------------------------------------------------------------------

2. Max Consecutive 1s- (III)

(with at most K zeros)

Brute- time: O(n^3)

1. Try every subarray
2. For every (i,j): count how many zeros are in v[i..j]
3. If zeros ≤ k, update answer

-----------------------------------------------

Better- time: O(n^2)

instead of using a for loop to count no. of zeros in i to j, we use prefix array to store at every index how many zeros are from 0 to i, thus-

no. of zeros from i...j = ( pref [j] - pref [i-1] )
---------------------------------------------

Optimal- time: O(n)

use sliding window pattern-3

---------------------------------------------------------------------------------------------------------------------------

3. Fruits into Baskets-
( Longest subarray with at most 2 distinct elements )

Brute- time: O(n^2)    space: O(n)

using 2 for loops & a set

----------------------------------------------------
Optimal- time: O(2n)   space: O(n)

use, sliding window + hashmap
here, k = 2

-----------------------------------------------------------------------------------------------------------------------------

4. Longest repeating character replacement

Longest substring that needs at most k changes to become all same characters. ---------------------------------------------------
Brute-  time: O(n^2)

for every substring,
check if, maximum frequency waale character ke alawa jo bache hue characters hai
unka count <= k

-------------------------------------------------------------

Optimal- time: O(n)⭐

using sliding window pattern-2
IMP- in every iteration max freq is recalculated...

----------------------------------------------------------------------------------------------------------------------------

5. Count binary subarrays with sum=K 

Optimal- time: O(n)

using my sliding window pattern-3 of :
count(=k) = count( <= k) - count( <= k-1)

-----------------------------------------------------------------------------------------------------------------------------

6.  Count nice subarrays-
(i.e., with k odd numbers)

Brute- time: O(n^3)     space: O(1)
use 2 loops to generate all subarrays and for each subarray from i to j, run another loop to count number of odd numbers in this subarray

-----------

Better- time: O(n^2)   space: O(n)

instead of running a third loop in brute force, we would use a prefix array storing number of odd numbers from 0 to index i at pref[i] , thus now we can find number of odd numbers in i to j, as 
pref [j] - pref [i-1]

-----------
Optimal- time:O(n)

use sliding window pattern 3 of mine-
count(=k) = count(<=k) - count(<= k-1)

-----------------------------------------------------------------------------------------------------------------------------

7. Substring containing all 3 characters-⭐

Brute- time: O(n^2)   space: O(1)

generate all substrings, keep a track of frequencies of all 3 characters, when frequencies of all three characters in a substring is non zero, then do cnt ++ 

----------------------------------------------------------------
Better- ⭐

instead of doing cnt++
we will do cnt += (n-j)
since when a first substring containing all 3 characters is found, then all later substrings also counted, hence we do (n-j) to count all later substrings (which are extension of current substring) at once.
----------------------------------------------------------

Optimal- time: O(n)⭐

using minimal valid window concept

for every i, we will find first valid substring starting from i-th index, and then cnt all valid substrings starting from this index...

-----------------------------------------------------------------------------------------------------------------------------

8. Max points from exactly K cards-

Optimal- time: O(n)     space: O(1)

Using sliding window pattern-1
or, find max sum by picking k elements from ends
ans = (total Sum) - (min sum window of length n-k)

--------------------------------------------------------------------------------------------------------------

9. Longest substring with at most K distinct characters-

Brute- time: O(n^2)    space: O(k)

we will generate all substrings and find maximum length required.

-----------------------------------------
Optimal- time: O(n)     space: O(k)

Using sliding window pattern-2

--------------------------------------------------------------------------------------------------------------

10. Count subarrays having K different integers-

Brute- time: O(n^2)   space: O(k)

we will generate all subarrays and count those which have k distinct integers.

--------------------------------------------------
Optimal- time: O(n)  space: O(k)

using sliding window pattern:     exactly K = ( atmost k - atmost (k-1) )

we can further optimise by using freq vector & a distinct counter instead of a map
freq vector will be of size n+1 to directly map freq with element

-----------------------------------------------------------------------------------------------------------------------------

11. Minimum window substring-⭐⭐

Brute- time: O(n^3)

For each substring, we generate freq array and compare this with freq array of string t & everytime see if all characters of t are in current substring or not

---------------------------
Better- time: O(n^2)

instead of creating frequency array for each substring 
we instead create a dynamic frequency array for substrings starting from index i
and as soon as we find a valid substring we break, since we need smallest

Alter- instead of doing 256 character check, we can also prefer to reduce character freq of characters in t & maintain a cnt variable of how many are done uptill now...
--------------------------------------------------------

Optimal- time: O(n)

using sliding window

for every i, we find first j which makes window valid
Observation- window only moves forward, hence j is monotonic...
instead of resetting j from every i, we start j from its past value for prev i

1. build freq array for t
2. start with an empty window
3. expand right pointer & reduce its needed cnt from freq array. once u fulfilled a character, reduce missing by 1
4. when missing becomes 0, then window contains all characters of t, now shrink from left to make window shortest valid window
5. update answer
6. repeat from step 3

---------------------------------------------------------------------------------------------------------------------------