Got this question in Amazon OA.
I tried to generate all the substrings at every index and checked if it is a valid substring or not. I know it's not efficient but I still tried and wrote the code, I was able to pass only half of the test cases and got TLE for other test cases.
I would like to see other approaches to solve the problem.