Lcs doubt on submission

#1


sir it is giving runtime please check

#2

@Shivanchal-Agarwal-2530139037020445
I have solved the runtime error, it was because you were making array of ~1e6, in a function. It has to be declared in heap.
but this will give TLE because it is O(n^3) in complexity.
Corrected code : https://ide.codingblocks.com/s/290411
O(n^2) code : https://ide.codingblocks.com/s/290406?_ga=2.123956682.1389215852.1595335586-514560086.1580045254

#3

sir how is it O(n^3) ?
its not n^2?

#4 
dp[i + 1][j + 1] = dp[i][j] + s[i];

This step is O(N)

#5

can you please explain how is this O(n)?
i cant understand

#6
  1. the length of the string can be of order N.
  2. when you assign string a = “abc…” this operation is in the order of the length of the string.
#7

but sir on this step we are just assigning the values from the dp array and string right?
so shouldn’t it be a constant complexity rather than linear?

#8

while assigning the values, a fresh copy of the string is created which gets copied and then it is assigned the dp array. making a fresh copy of string of size N, takes O(N) time.

#9

I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.

On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.