Please read the new rule regarding the restriction on the use of AI tools. ×

Doubt in Required Substring CSES problem

Revision en1, by Surge226, 2024-08-10 15:46:45

Hello everyone, I am trying to solve Required Substring problem from CSES.

First of all, I tried to solve it using combinatorics. My idea was that consider $$$n=6$$$ and string $$$s=$$$ABCDB with 5 characters, then the number of ways we can make $$$n$$$ character string with string $$$s$$$ in it, would be to fix string $$$s$$$ at first position in $$$n$$$ characters and fill rest positions with $$$26$$$ characters, giving $$$numberOfWays = 26$$$. Then, we can shift the substring for $$$(n - m)$$$, i.e, $$$6 - 5 = 1$$$ times to right, and we would get $$$numberOfWays = (n - m + 1) * 26^{(n - m)}$$$, which would, for sample test case, result in $$$numberOfWays = (6 - 5 + 1) * 26^{(6 - 5)} = 52$$$

But, it failed for this test case $$$n=6$$$ and $$$s=$$$ AA. And, I am not able to figure it out, why this is not working because of the large output.

Then, I peeked the solution here, and tried it to code myself, but in the end it is not working. My idea was same as the solution, that is, to build string character by character, and we track progress of building required string as our substring.

My Code

And, the Solution is following slightly different approach.

Solution

I think my code is faulty at many places but if someone can tell what mistakes my code is doing, or even the main problem of my code, then it would be really helpful for me.

Thanks

Tags required substring, cses, combinatorics

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en1 English Surge226 2024-08-10 15:46:45 3865 Initial revision (published)