Longest Substring With Exactly K Unique Characters

faq

1. What does the term "Longest Substring With Exactly K Unique Characters" mean?
Ans -> Substring that contains exactly k number of unique characters and we need to return its length.

2. How can we use HashMap into this question?
ans -> We are using Aquire and Release strategy, and HashMap for storing k number of unique characters and when we have HashMap's size is equals to k then we can calculate length of longest substring present with the help of aquire and release pointer.

3. While using HashMap why our time complexity is O(n + k) and why not O(n ^ k) and other?
ans -> Because we are storing at max k characters into HashMap

4. Can we use HashSet instead of HashMap?
ans -> No, for this perticular question we want the characters with their occurences and into HashSet we cannot store both values.

5. How we are ensure the count of substring that contains (k OR k - 1) unique characters?
    Where,
        i = aquire pointer
        j = release pointer
ans -> this will gives the count of substring for (k OR k - 1) unique character = substracting j from i + 1

hints

1. Can you think any approach by using a HashMap?
2. Try using a two-pointer approach.
3. The right pointer moves till the number of unique characters are less than or equal to K. 
4. As the unique characters exceed K, the right pointer stops. 
5. Then, the left-pointer moves to exclude the minimum elements from the current window such that the unique element again become equal to K.

mcq

1. What is the Time Complexity to solve this question?      
a. O(n+k)
b. O(n * logn)
c. O(n * k)
d. O(1)

Ans : a. O(n + k)
Explaination : We are storing at max k characters into Hashmap.

2. What is the Space Complexity to solve this question?
a. O(n * k)
b. O(n + k)
c. O(k)
d. O(1)

ANS : b. O(n+k)
Explaination : We are storing at max k characters into Hashmap.

3. A. which of the following is the substring of "pepcoding"?
a. ppodng
b. ecoig
c. pep
d. none of the above

Ans -> c pep
Explaination : pep is in continuous order

4. As per the question, if String = "aabcb", k = 2, then which of the following is the answer?
a. bcb, bc, bac, cb
b. aab, ab, bcb, bc
c. aabac, aab, ab, bcb
d. cb, ab, aabac, bc

Ans -> b. aab, ab, bcb, bc
Explaination : all substring have k unique characters

5. what should we store in our HashMap ?
a. Character with their index
b. Character with their occurences
c. Distinct Character
d. None of the above

Ans -> b. Character with their occurences
Explainations : For finding the distinct we are storing Characters with their occurences