Problem: 1927B - Following the String
My 1st approach:277732437 — Gave TLE on test 3
Read editorial, understood that their approach was similar but they did not store the alphabets, they only stored the count.
2nd submission after reading editorial:277733314 — Still gave TLE on test 3
Tried to submit the exact code given in the editorial(277733398) — Still gave TLE on test 3
Can someone please suggest a better way of solving it?(I went through a few submissions but they did the same thing and got AC so i was confused about what was wrong in my submissions)(Or some of the other submissions which were different, i could not exactly grasp what they were trying to do/what approach they followed)
Auto comment: topic has been updated by ApaarGulati (previous revision, new revision, compare).
The problem lies in the line:
s += chr(97 +j)
Adding to a string in Python (in this case to s) works for O(len(s)), because strings in Python are immutable objects and in fact this line created a new string with length len(s) + 1, and since it is in a loop, it turned out that the asymptotics are not O(n), and O(n^2), which led to TLE
Instead of a string, try using an array and adding elements to it
oh ok thanks a lot.
but actually, there were submissions like 275104852 and 274045809 in which even strings were working so i wad a bit confused.
but thanks a lot. i will keep this in mind from next time. :)