Grokking the Coding Interview: Patterns for Coding Questions

0% completed

​

Solution: Longest Substring with K Distinct Characters

Problem Statement

Given a string, find the length of the longest substring in it with no more than K distinct characters.

You can assume that K is less than or equal to the length of the given string.

Example 1:

Input: str="araaci", K=2  
Output: 4  
Explanation: The longest substring with no more than '2' distinct characters is "araa".

Example 2:

Input: str="araaci", K=1  
Output: 2  
Explanation: The longest substring with no more than '1' distinct characters is "aa".

Example 3:

Input: str="cbbebi", K=3  
Output: 5

.....

.....

.....

Like the course? Get enrolled and start learning!
N

Nikhil Srivastava

· 5 years ago

Its bit difficult to my head get around this implementation since in the previous problems we have been adding the character to the map first.. I think having a pictorial representation would have helped a lot..

Show 3 replies
Ariel Davies

Ariel Davies

· 2 years ago

The current solution uses while(Object.keys()) which increases the time complexity from O(N) to O(N * K) where K is each key in the object that has to be added again into an array for each iteration.

The optimal solution would instead have an int as the counter which gets us back to O(N).

P

Pratik

· 4 years ago

windowStart = Math.max(windowStart, charIndexMap.get(rightChar) + 1);

Any example of this happening? I cant think of an example where windowStart is greater than rightChar ?

Please elaborate.

Show 3 replies
A

ag

· 4 years ago

how about this solution, basically once we encounter a duplicate then just clear the set

int windowStart = 0, maxLength = 0; Set cache = new HashSet(); for (int windowEnd = 0; windowEnd < str.length(); windowEnd++) { char c = str.charAt(windowEnd); if (cache.contains(c)) { cache.clear(); windowStart = windowEnd; } cache.add(c); maxLength = Math.max(maxLength, windowEnd - windowStart + 1); }

return maxLength;

Show 1 reply
S

Sourav Rawat

· 4 years ago

This is one that is causing me a lot of trouble https://leetcode.com/problems/sliding-window-maximum/

Show 1 reply
A

Anthony DiFede

· 4 years ago

I believe I accounted for the edge cases... As long as you encounter a letter you've seen before, make the window start = window end since you will only be caring about a substring with no duplicates. Image

R

Rodney

· 4 years ago

Out of curiosity, why is the time complexity O(N) and not O(N*K)

Show 2 replies
J

Joshua Causey

· 4 years ago

Does anybody have an edge case where you need to set windowStart like this windowStart = Math.max(windowStart, map[rightChar] + 1

Because if I just set it to map[rightChar] + 1 it works for every case I have. Really want to understand this. Even just an example string I could debug would be great ❤️

Show 1 reply
N

Ngân Nguyễn

· 4 years ago

I didn't really get the window " In the current window, ...." . Can anyone explain that? Tks in advance.

Show 1 reply
Y

Yogi Paturu

· 5 years ago

Why can't you insert rightChar into the map first and then update widowStart, such that it's the max of windowStart and the index of rightChar? It seems to be equivalent to me, but swapping the order of the if condition and updating the charIndexMap doesn't work

Anyone have any insight into this?

Show 3 replies