https://www.acmicpc.net/problem/5525
initial
my initial runtime ineff code:
n = int(input())
m = int(input())
hola = input()
count = 0
check = "I" + "OI" * n
length = len(check)
for i in range(m - length + 1):
if hola[i:i + length] == check:
count += 1
print(count)well while the ans is correct, it causes runtime for mega big inputs. Also, i didnt know the time complexitiy of slicing list is lst[a:b] has time of o(b-a).
So if the sublist to be sliced and compared is very long (due to large n), then this contributes to time inefficiency. We want to be slicing minimally in small sizes. So since the pattern is "IOI" (not produce 101), why dont we slice by [i:i+3] and if it is equal to "IOI", we increment tmp variable? We use a while loop where index i is less than m(string's length). If tmp variable equals n, we know that the whole thing is equal to our check string of IOIOIOIO..., so we increment count. Very important that we decrement tmp by 1 because we are incrementing index i by 2 so when we meet our answer condition, we have to decrement tmp because for the next iteration our i will be incremented by i, which excludes the first "IOI".
If the sliced sublist is not IOI, we increment i by and just reset tmp as 0 because we cannot have an invalid case in the middle of valid cases like IOI IIII IOI. This IIII cannot contribute to a correct case so tmp has to be reset.
solution
n = int(input())
m = int(input())
hola = input()
count = 0
i=0
tmp=0
while i<len(hola):
if hola[i:i+3]=='IOI':
tmp+=1
i+=2
if tmp==n:
count+=1
tmp-=1
else:
i+=1
tmp=0
print(count)time and space
oh the time complexity isnt affected by slicing [i:i+3] cuz as i said earlier, time of slicing list is 0(b-a) so it is o(3) = 0(1) constant time. SO the time is dominated by just the for loop iteration
The time complexity of this algorithm is O(m), where m is the length of the input string hola. In the worst case, the algorithm iterates through each character of the string once.
The space complexity is O(1) because the algorithm uses a constant amount of additional space regardless of the input size. The only variables used are count, i, and tmp, and they do not scale with the input size.
