Coding Week 6 - Sliding Windows Flashcards
Problem 1) Longest Substring With At Most K Distinct Characters
(Sliding window)
Given a string s and an integer k, return the length of the longest substring of s that contains at most k distinct characters.
Example 1:
Input: s = “eceba”, k = 2
Output: 3
Explanation: The substring is “ece” with length 3.
Question 1) What will be the space complexity of the sliding window approach, if the input string of length ‘N’ contains ‘K’ distinct characters and when it contains ‘N’ distinct characters?
(N -> length of input string)
A) O(N), O(N)
B) O(1), O(N)
C) O(N), O(1)
D) O(1), O(1)
D) O(1), O(1)
In the sliding window approach, we will maintain a hashtable to validate any window. If we try to expand the window and after adding the current character, the size of the hashtable exceeds k, then it means that the current window is not a valid window and we will remove the starting character of the sliding window from the hash table. Hence, at any point of time the space used is at most O(K). Here, the max value of ‘K’ can be 26 and O(26) = O(1)..
Problem 1) Longest Substring With At Most K Distinct Characters
(Sliding window)
Given a string s and an integer k, return the length of the longest substring of s that contains at most k distinct characters.
Example 1:
Input: s = “eceba”, k = 2
Output: 3
Explanation: The substring is “ece” with length 3.
Question 2) What will be the time complexity of the sliding window approach?
(N -> length of input string)
A) O(N)
B) O(K)
C) O(N * K)
D) O(1)
A) O(N)
Each character will get added or removed from the hash table only once.
Problem 2) Find all Anagrams in a String
(Sliding window)
Given two strings s and p, return an array of all the start indices of p’s anagrams in s. You may return the answer in any order.
An Anagram is a word or phrase formed by rearranging the letters of a different word or phrase, typically using all the original letters exactly once.
Example 1:
Input: s = “cbaebabacd”, p = “abc”
Output: [0,6]
Explanation:
The substring with start index = 0 is “cba”, which is an anagram of “abc”.
The substring with start index = 6 is “bac”, which is an anagram of “abc”.
Question 1)
The above problem can be solved using the Sliding window with Hash Table but not using the Sliding window with Array.
A) True
B) False
B) False
This problem can be solved using the Sliding window with Hash Table as well as using the Sliding window with Array.
Problem 2) Find all Anagrams in a String
(Sliding window)
Given two strings s and p, return an array of all the start indices of p’s anagrams in s. You may return the answer in any order.
An Anagram is a word or phrase formed by rearranging the letters of a different word or phrase, typically using all the original letters exactly once.
Example 1:
Input: s = “cbaebabacd”, p = “abc”
Output: [0,6]
Explanation:
The substring with start index = 0 is “cba”, which is an anagram of “abc”.
The substring with start index = 6 is “bac”, which is an anagram of “abc”.
Question The time and space complexity of sliding window with HashTable approach will be :
(N -> length of string ‘s’, M -> length of string ‘p’)
Question 2)
A) Time - O(N ^ 2), Space - O(N)
B) Time - O(M ^ 2), Space - O(N)
C) O(N + M), Space - O(1)
D) O(N * M) , Space - O(1)
D) O(N * M) , Space - O(1)
We have to iterate through strings ‘s’ and ‘p’ to find the frequency of each character in each string which will take O(N + M) or O(Max(N, M)) time.
There can be only 26 distinct characters, so we have to store a frequency of only 26 characters which will take constant space.
Problem 3) Sliding Window Maximum
You are given an array of integers nums, there is a sliding window of size k which is moving from the very left of the array to the very right. You can only see the k numbers in the window. Each time the sliding window moves right by one position.
Return the max sliding window.
Example 1:
Input: nums = [1,3,-1,-3,5,3,6,7], k = 3
Output: [3,3,5,5,6,7]
Explanation:
Window position Max
————— —–
[1 3 -1] -3 5 3 6 7 3
1 [3 -1 -3] 5 3 6 7 3
1 3 [-1 -3 5] 3 6 7 5
1 3 -1 [-3 5 3] 6 7 5
1 3 -1 -3 [5 3 6] 7 6
1 3 -1 -3 5 [3 6 7] 7
Question 1)
What will be the time and auxiliary space complexity of the following approach?
(N -> nums.length, NGE -> next greater element)
Find the next greater element for each element in ‘nums’ and store them in the NGE array.
Declare a variable j (=0).
Iterate i from 0 to N - k
if(j < i)
j = 1.
While (NGE[j] < i + k)
If(NGE[j] != -1)
j = NGE[j].
Else break.
Print arr[j].
A) Time - O(N ^ 2), Space - O(N)
B) Time - O(1), Space - O(1)
C) Time - O(N), Space - O(N)
D) Time - O(N), Space - O(1)
C) Time - O(N), Space - O(N)
Finding the next greater element of each element in nums, will take O(N) time.
There can be at most N jumps over all iterations of ‘i’ of the next greater elements(a jump denotes (j = NGE[j])). Hence, the time complexity will be O(N).
Storing the next greater element of each element in nums will take O(N).
Problem 3) Count Binary Substrings
Given a binary string s, return the number of non-empty substrings that have the same number of 0’s and 1’s, and all the 0’s and all the 1’s in these substrings are grouped consecutively.
Substrings that occur multiple times are counted the number of times they occur.
Example 1:
Input: s = “00110011”
Output: 6
Explanation: There are 6 substrings that have equal number of consecutive 1’s and 0’s: “0011”, “01”, “1100”, “10”, “0011”, and “01”.
Notice that some of these substrings repeat and are counted the number of times they occur.
Also, “00110011” is not a valid substring because all the 0’s (and 1’s) are not grouped together.
Question 1) What will be the time and space complexity of the following approach?
-> Convert the string ‘s’ into an array ‘groups’ that represents the length of same-character contiguous blocks within the string. For example, if ‘s’ = “110001111000000”, then groups = [2, 3, 4, 6].
-> Now, If we have groups[i] = 2, groups[i+1] = 3, then it represents either “00111” or “11000”. We clearly can make min(groups[i], groups[i+1]) valid binary strings within this string. Because the binary digits to the left or right of this string must change at the boundary, our answer can never be larger.
A) Time - O(N ^ 2), Space - O(N)
B) Time - O(1), Space - O(1)
C) Time - O(N), Space - O(N)
D) Time - O(N), Space - O(1)
C) Time - O(N), Space - O(N)
O(N) to create ‘groups’ and O(N) to iterate through ‘groups’. Hence, the time complexity will be O(2 * N) = O(N).
O(N) space will be taken by ‘groups’.
Problem 3) Count Binary Substrings
Given a binary string s, return the number of non-empty substrings that have the same number of 0’s and 1’s, and all the 0’s and all the 1’s in these substrings are grouped consecutively.
Substrings that occur multiple times are counted the number of times they occur.
Example 1:
Input: s = “00110011”
Output: 6
Explanation: There are 6 substrings that have equal number of consecutive 1’s and 0’s: “0011”, “01”, “1100”, “10”, “0011”, and “01”.
Notice that some of these substrings repeat and are counted the number of times they occur.
Also, “00110011” is not a valid substring because all the 0’s (and 1’s) are not grouped together.
Question 2)
Can you solve this problem in O(1) space?
A) Yes
B) No
A) Yes
Instead of storing groups, we will remember only previous group. Then, the answer is the sum of min(previous, current) over each different final (previous, current) we see.
