我的代码在竞赛平台上出现了时间限制错误

Question

我想在网上打码平台（下面给出的问题）用下面的代码解决这个问题。竞赛平台显示时间限制错误。

问题。

Tahir和Mamta正在TCS的一个项目中工作。Tahir作为一个问题解决者，为他的朋友Mamta提出了一个有趣的问题。

问题由一个长度为N的字符串组成，并且只包含小写字母。

它的后面将有Q个查询，其中每个查询将包含一个整数P(1<=P<=N)，表示字符串中的一个位置。

Mamta的任务是找到存在于该位置的字母，并确定相同字母在给定位置P前的出现次数。

Mamta正忙于她的办公室工作。因此，她请你帮助她。

限制条件

1 <= N <= 500000。

由小写字母组成的S

1 <= Q <= 10000。

1 <= P <= N。

输入格式第一行包含一个整数N，表示字符串的长度。

第二行包含字符串S，本身只包含小写字母（'a' - 'z'）。

第三行包含一个整数Q，表示将被询问的查询次数。

接下来的Q行包含一个整数P(1 <= P <= N)，你需要找到P前面第1个位置的字符的出现次数。

输出对于每个查询，在单行上打印一个表示答案的整数。

时间限制

1

我的代码

n=int(input())
a=input()[:n]
for i in range(int(input())):
    p=int(input())
    print(a[:p-1].count(a[p-1]))

输入，输出的样本

例一

输入

9

abacsddaa

2

9

3

产量

3

1

解释

这里Q=2

对于P=9，第9位的字符是'a'。在P前出现'a'的次数，即9是三个。

同理，对于P=3，第3个字符是'a'。在P前出现'a'的次数，即3是1。

我是Python新手，所以请帮助我解决这个错误。

Answer 1

你的解决方案的复杂度是O(n²)而导致时间限制错误。prefix sum array 算法。看看这个 联系 并为每个字母定义一个前缀和数组。