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 PyPy (in this case to s) works for O(len(s)), because strings in PyPy 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. :)
Yes, I made a mistake (corrected the previous comment from Python to PyPy)
Adding a character to a string in Python and PyPy work differently, your submit was made on PyPy, just in it adding to a string works for O(len(s)), those submits that received AC are sent to Python, in it adding to a string works for O(1)
ohh. ok
i get it now. Thanks a lot!! :)
IMPOSSIBLE??