CODEWITHSUNDEEP
pythonpython-3.xstring
Polar
Polar

Reputation: 63

Efficient way to count occurence of a certain character in string?

Here is link to the problem from a contest(which has ended): https://justpaste.it/7g5bz

I have tried this approach.

p = []
n = int(input())
s = input()
q = int(input())
for _ in range(q):
  p.append(int(input()))
for pth in p:
  print(s.count(s[pth-1],0,pth-1))

Test cases are running fine but when I submit this solution. It is showing Time Limit Exceeded. Is there any other more optimized way?

Upvotes: 0

Views: 86

Answers (1)

Andrej Kesely
Andrej Kesely

Reputation: 195408

It's timing out because you are calling count() in a loop:

I would as first step preprocess the input string: create new list containing number of how many times the character occurrs before in the string. That way the querying the count of occurrences of character at certain index will become O(1):

s = 'abacsddaa'

from itertools import count
from collections import defaultdict

d = defaultdict(count)
new_s = [next(d[ch]) for ch in s] # new_s is [0, 0, 1, 0, 0, 0, 1, 2, 3]

count_occurences = lambda idx: new_s[idx-1] 


print(count_occurences(9))
print(count_occurences(3))

Prints:

3
1

Upvotes: 1

Related Questions