Given a string, we want to know the maximum no. of occurrences of any substring that satisfies following two conditions:
For example, given a string s=abcde, minLength=2, maxLength=5, maxUnique=3, the substrings matching the criteria are (ab, bc, cd, de, abc, bcd, cde). Any shorter string fails he INPUT : First line contains a string, second line contains minLength, third line contains maxLength, and the last line contains maxUnique. Constraints :
SAMPLE INPUT :
SAMPLE OUTPUT :
EXPLANATIONS : We want to find the no. of occurrences of the most frequently occurring substring of s= "ababab" that has the length in the inclusive range from minLength = 2 and maxLength=3 and contains maximum of maxUnique = 4 unique characters. The substring ab occurs three times aba, bab and ba occurs twice. Because we want maximum of this frequencies we return 3 as our answer. asked 01 Sep '18, 10:43

(Part 1) Obviously we shouldn't care for maxLength,since we wanna maximize ocuurrence(as lets say if a substring of length x,occurs y times,then there must be a substring of length (x1) that occurs>=y times) So we just have to find max no.of occurrences of a substring of length minLength (Part 2) unique thing can easily be done using frequency arrays (Part 3) One simple way is to use rolling hashing see this: https://threadsiiith.quora.com/StringHashingforcompetitiveprogramming for counting max occurence of a substring of given length (Part 1) Proof: Lets say a substring s of length x occurs b times,then there will be a substring s' of length < x occuring >=b times(1 such substring would be a substring of s) like ababa ab occurs 2 times,so obviously a occurs>=2,b>=2 So better to find minimum Length String,as it will have less unique characters and also occurs greater number of times (Part 2) how to check if a substring s[i:j] is valid (no.of unique characters<=maxUnique) lets construct a prefix sum freq array where: freq[i]['a']=freq[i1]['a']+(s[i]=='a') freq[i]['b']=freq[i1]['b']+(s[i]=='b') ...... So for calculating no.of unique characters in s[i:j]
(Part 3) we can now iterate for all substring of length minLength so :
answered 01 Sep '18, 11:38
Can you please provide more detailed explanation, I am finding it hard to understand.
(01 Sep '18, 22:20)
OOh sorry,for the late reply!! These bugs...
(03 Sep '18, 14:10)
I have got the idea from the explanation and the link, can you explain me about implementing hashing. I have encountered this kind of problem for the first time that's why I am facing difficulty.
(30 Sep '18, 16:44)
If u had sincerely read the link ,u wouldn't have asked this..:(. Plz read from link,and do a bit of searching too!!,i don't support spoon feeding...
(04 Oct '18, 10:21)
@vivek_1998299 In the worst case, Time complexity of your approach is O(N^2). Is there any O(N log N) algorithm for the same thing?
(20 Dec '18, 19:25)
@vivek_1998299 In the worst case, Time complexity of your approach is O(N^2). Is there any O(N log N) algorithm for the same thing?
(20 Dec '18, 19:26)
showing 5 of 6
show all

@l_returns @jimmy51997 @vijju12 @inishchith @ankit_gupta_ @rachitiitr @taran_1407 @kal013 @joffan @inseder @kauts_kanu
Can anyone help me with this problem.