Help me out in one leetcode problem

#1


leetcode submission

leetcode question

#2

@aman212yadav are u there?

#3

yeah ,pls tell me what issue u r facing

#4

@aman212yadav in this problem 34 testcases are passed but in last case it is giving tle but my time complexity is 10^6 just have a look into my code

#5

how… ?

#6

always express complexity in terms of input size

#7

klogk+(n+k-1)
klogk is sort each plength substring
n+k-1 will be number of such substring
@aman212yadav

#8

@shivammishra20121999
let
S is the size of Bigger string and p is the size of pattern.
then total S-p+1 will the number of substrings right?
and for each p size substring u will perform following operations.
a) obtain that substring which is O( p)
b) then u will sort it which is p log p
c) then u match which is O(1)
so overall p + plog( p) + 1 per substring
in total it will be
(S-p+1) * (p+p log( p)+1)

#9

@aman212yadav tc in my case in worst case will be o(n^2) rigth?
then it should accept

#10

roughly it will be s * p * log( p ) and as per mentioned constraints it will fail for some cases.

#11

@aman212yadav okay thks any other logic migth work here

#12

@aman212yadav frequency of character plus sliding window will work here

#13

yeah …it will

#14

@aman212yadav ok thanks