15,997,776 members
See more:
string S of length N consisting only of 0s and 1s.
Q queries. In the ith query, two integers Li and Ri are given.
S[L, R] denotes the substring from Lth to Rth characters of the string S.
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.

and sample input is
1
8 2 3
01110000
1 4
2 4
5 8

What I have tried:

Python
```T= int(input())
for _ in range(T):
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]
if y.count(1)<=K and y.count(0)<=K:
ans+=1
print(ans)```

Posted
Updated 9-May-21 7:58am
v4
Patrice T 5-May-21 3:46am
Looks like a part of problem is missing.
Did you shortened the requirement ?

Give a link to the problem.
Muskan Verma 2021 5-May-21 5:01am
You are given a string S of length N consisting only of 0s and 1s. You are also given an integer K.

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.
Patrice T 5-May-21 5:04am
I ask for URL because in such challenge, very word count.
In the question, result for sample input is missing.
Muskan Verma 2021 5-May-21 5:13am
https://www.codechef.com/LRNDSA04/problems/STRSUB
Richard MacCutchan 10-May-21 4:49am
See my comment to your previous question: Do not save numeric variables as strings, so that you need to convert them to integer for each calculation. Convert them once so your program runs faster.

Solution 1

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

Because you have nested loops everywhere.
Python
```# loops in each query,
L , R = list(map(int,input().split()))
#       ^ loop nest 1 here
res = [S[i : j] for i in range(L-1,R+1) for j in range(i+1,R+1)]
#               ^ Loop nest 1 here
#                                       ^ Loop nest 2 here
ans = 0
for x in res:
# ^ Loop nest 2 here
y = [int(i) for i in x]
#           ^ Loop nest 3 here
if y.count(1)<=K and y.count(0)<=K:
#    ^ Loop nest 3 here
#                      ^ Loop nest 3 here
ans+=1
print(ans)
```

Python is loaded with comfortable features, but it cost.
You need to think smart, this code is brute force.
[Update]
If I understand your code corectly,
Python
```y.count(1)+ y.count(0) is length of y
# one of the count loop can be removed.```

Hint: you have a constant string of 1's and 0's, can you find a way to get the count of 1's between 2 arbitrary positions without recounting the 1's every times.

v3
Muskan Verma 2021 5-May-21 4:56am
thanks for ur guides

Solution 2

I'm far from a python expert, but these things I think you could do to improve your code almost universal:

• Name your variables something meaningful. `L` and `R` don't mean very much `left_character_position`; and `right_character_position`; do. The big exception is `i` in iteration. Use a style guide a style guide[^] and the general principle applies to all things you name - again Python has its own rules. If you teacher/lecturer is telling you to do this, keep doing it or prepare to justify why they are wrong (and they are). The original reason for short variable names - lack of memory on the dev's machine, chonky editors & limited screen space, is no longer relevant
• Each branching statement (this includes loops and if statements) increases complexity greatly. You'd think there is nothing you can do about this - but the block inside a if/loop is nearly always a candidate to be refactored as a function. The fact you have to comment up nested loops should tell you something.
• The method looks brute force - sit down with a paper and pencil to see if you can make the task easier, using sample lists
• Python is pretty rich - I dare say there are features you can use to make this task easier.

Most of this is a recap of PatriceT's reply, but hopefully it's useful.

v2

Solution 3

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 onFormulaComplexity
Chars of string=nO(n)
Number of sub-strings=(n*(n+1))/2O(n2)
Chars of all sub-strings=(n*(n+1)*(n+2))/6O(n3)

Cost of Activityn= 10n= 100n= 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.

Python
```N , K , Q = list(map(int,input().split()))
# get string O(n)
S = str(input())
for _ in range(Q):
L , R = list(map(int,input().split()))
# Generate all sub-strings O(n<sup>2</sup>)
res = [S[i : j] for i in range(L-1,R+1) for j in range(i+1,R+1)]
ans = 0
# loop on all sub-strings O(n<sup>2</sup>)
for x in res:
# Convert all digit to integer  O(n<sup>3</sup>)
y = [int(i) for i in x]
# Count all 1  O(n<sup>3</sup>)
y1= y.count(1)
# Count all 0  O(n<sup>3</sup>)
y0= y.count(0)
if y1<=K and y0<=K:
ans+=1
print(ans)```

- convert to ints only once saves 33% of runtime
Python
```N , K , Q = list(map(int,input().split()))
# get string O(n)
S = str(input())
# Convert all digit to integer  O(n)
S2 = [int(i) for i in S]
# Change rest of code to work on S2, as array of integers
for _ in range(Q):
L , R = list(map(int,input().split()))
# Generate all sub-strings O(n<sup>2</sup>)
res = [S[i : j] for i in range(L-1,R+1) for j in range(i+1,R+1)]
ans = 0
# loop on all sub-strings O(n<sup>2</sup>)
for x in res:
# Convert all digit to integer  O(n<sup>3</sup>)
y = [int(i) for i in x]
# Count all 1  O(n<sup>3</sup>)
y1= y.count(1)
# Count all 0  O(n<sup>3</sup>)
y0= y.count(0)
if y1<=K and y0<=K:
ans+=1
print(ans)```

- Do not count 0s save another 33% of runtime
Python
```N , K , Q = list(map(int,input().split()))
# get string O(n)
S = str(input())
# Convert all digit to integer  O(n)
S2 = [int(i) for i in S]
# Change rest of code to work on S2, as array of integers
for _ in range(Q):
L , R = list(map(int,input().split()))
# Generate all sub-strings O(n<sup>2</sup>)
res = [S[i : j] for i in range(L-1,R+1) for j in range(i+1,R+1)]
ans = 0
# loop on all sub-strings O(n<sup>2</sup>)
for x in res:
# Count all 1  O(n<sup>3</sup>)
y1= y.count(1)
# Count all 0  O(n<sup>3</sup>)
y0= y.count(0)
# calc numbze of 0  O(n<sup>2</sup>)
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.

I let you deal with details for final code.

v3