P#13 K-distinct Substring

All problems are from https://www.dailycodingproblem.com/

 

My Solution Codes : https://github.com/Kusin/DailyCoding

Kusin/DailyCoding

Daily Coding Problem# 13: K-distinct Substring 

Problem Description

 

Idea

Time Complexity : O(n)

Let's Use Two Pointers. 

Starting from s=0, e=0, we will sequentially watch the string. 

If str[s] ~ str[e] contains more than k characters, increase s.

else update answer and increase e.

 

How to check distinct characters of str[s] ~ str[e]? 

We can use a list to count each chararcters and a variable to carry numbers of distinct characters.

Or, simply use dictionarys and len(dict.keys()) method. (which will take more time than using list)

 

Is this a correct algorithm? 

Idea Source : https://m.blog.naver.com/kks227/220795165570 (if you know Korean, u can read it)

 

Let's think of a situation that our pointer is at s,e. 

And some section [S,E] : S>s , E>e  exists and contains equal to or less than k distinct characters. Also, suppose that E-S is Max. (Which means that the section is the answer).

if our pointer doesn't count the following section, there are 2 cases.

 

Case#1 : s becomes s>S before e=E 

There is a moment which s = S.

By the sumption, section [S,e] contains equal to or less than k distinct characters since e<E.

Therefore, e will be increased untill e=E. Case#1 never happens.

 

Case#2 : e becomes e>E before s=S

There is a moment which e=E.

This case implies that there is a section [s',E] and s'<S. Since e will increase since e>E, it means that the section [s',E] contains equal to or less than k distinct characters. Note that [s',E] 's range is longer than [s,E]. It is a contradiction to the sumption that [S,E] is the longest section. Thus, Case#2 never happens.

For conclusion, we proved that using 2 pointers in this problem is correct.

Implementation :