Quote:

Why my code is not good in terms of time complexity?

I found the maths for this problem:

- The number of sub-string in a given string is a triangular number:

Triangular number - Wikipedia[

^]

- The number of char in all the sub-strings is a Tetrahedral number:

Tetrahedral number - Wikipedia[

^]

With a string of size n:

Activity on | Formula | Complexity |
---|

Chars of string | =n | O(n) |

Number of sub-strings | =(n*(n+1))/2 | O(n^{2}) |

Chars of all sub-strings | =(n*(n+1)*(n+2))/6 | O(n^{3}) |

Cost of Activity | n= 10 | n= 100 | n= 1,000 |
---|

Get length of string | = 1 | = 1 | = 1 |

Operation on chars of string | = 10 | = 100 | = 1,000 |

Count of sub-strings | = 1 | = 1 | = 1 |

Operation on sub-strings | = 10*11/2= 55 | = 100*101/2= 5,050 | = 1000*1001/2= 500,500 |

Count of char of sub-strings | = 1 | = 1 | = 1 |

Operation on chars of sub-strings | = 10*11/12/6= 220 | = 100*101/102/6= 171,700 | = 1000*1001*1002/6= 167,167,000 |

String size can go up to 300,000 chars.

Complexity of your code

N , K , Q = list(map(int,input().split()))
S = str(input())
for _ in range(Q):
L , R = list(map(int,input().split()))
res = [S[i : j] for i in range(L-1,R+1) for j in range(i+1,R+1)]
ans = 0
for x in res:
y = [int(i) for i in x]
y1= y.count(1)
y0= y.count(0)
if y1<=K and y0<=K:
ans+=1
print(ans)

Improving your code:

- convert to ints only once saves 33% of runtime

N , K , Q = list(map(int,input().split()))
S = str(input())
**S2 = [int(i) for i in S]**
for _ in range(Q):
L , R = list(map(int,input().split()))
res = [S[i : j] for i in range(L-1,R+1) for j in range(i+1,R+1)]
ans = 0
for x in res:
~~y = [int(i) for i in x]~~
y1= y.count(1)
y0= y.count(0)
if y1<=K and y0<=K:
ans+=1
print(ans)

- Do not count 0s save another 33% of runtime

N , K , Q = list(map(int,input().split()))
S = str(input())
S2 = [int(i) for i in S]
for _ in range(Q):
L , R = list(map(int,input().split()))
res = [S[i : j] for i in range(L-1,R+1) for j in range(i+1,R+1)]
ans = 0
for x in res:
y1= y.count(1)
~~y0= y.count(0)~~
**y0= y.length- y1**
if y1<=K and y0<=K:
ans+=1
print(ans)

- Remove counting 1s in every sub-string

Using a rule, it is easy to get number of centimeters between 2 arbitrary positions.

Make a rule counting 1s

01110000 String
001233333 Rule of 1s

A simple subtraction gives number of 1s in given sub-string.

You don't need to generate the sub-strings, just the count of 1s and 0s.

- Last, count sub-strings in lots

Say maximum is 3
01110000 Input
xxxxxx First longest sub-string matching criteria
xxxxxx Second
xxx third

When you have a string matching criteria, you know that any sub-string will match too, just calculate number of sub-strings.

When you have a longest string matching creteria, you know that no longer string will match, no need to search them.

Taking advantage of all this lead to complexity of almost O(n).

I let you deal with details for final code.

Did you shortened the requirement ?

Give a link to the problem.

You have to answer Q queries. In the ith query, two integers Li and Ri are given. Then you should print the number of substrings of S[L, R] which contain at most K 0s and at most K 1s where S[L, R] denotes the substring from Lth to Rth characters of the string S.

In other words, you have to count number of pairs (i, j) of integers such that L ≤ i ≤ j ≤ R such that no character in substring S[i, j] occurs more than K times.

In the question, result for sample input is missing.