I have written an O(n) solution using DFS but still i am getting TLE on test number 29. I don't understand why and hence i am unable to resolve the issue. I also tried using fast cin and cout but still i am getting TLE. Here is the link to the problem and link to my solution.
The problem is
word = word + s[i];
.The compiler interpret it as
word.operator=(word.operator+(s[i]));
, and bothstring::operator+
andstring::operator=
is O(n). So the loopis O(n2). You can generate a very long comment "ccccccc...c,0" and test your program with it. To fix this use
word += s[i]
. It's amortized time complexity is O(1).In C++,
a += b
is not exactly same asa = a + b
. Actually they can be totally different.Thank you for the help. I did not know that. Got an AC after making that change.