# Doubt in CHSTR

Can anyone please explain this ->

" From the above array we can conclude that we have 1 substring which can be choosen atleast 3 times. How? Because there are 3 entries in the above array that are greater than or equal to 1. Similarly we can deduce for 2 (2 times), 3 (2 times), 4 (1 time ) and 5(1 time). So we increment cnt[3] once, cnt[2] twice and cnt[1] twice. " ??

Specially in first sentence (from above quote) what is use of selecting 1 substring atleast 3 times ? Why would we so that ? and What will be the result of doing that ?

This is the algorithm with which we populate the `cnt` array. It means that we can find the same substring with length 1 three times. In that the case we can find the substring ‘a’ in three different places. Then we can find the same substring with length 2 two times (this is ‘ab’), and so on.

Then we repeat the same procedure with the next suffix.

At the end we will have populated the `cnt` array and we can compute the answer the way it is described at the beginning.

PS. “we have 1 substring which can be choosen atleast 3 times.” means the substring with length 1.

1 Like
//