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

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 之前第 P 个位置出现的字符的出现次数。

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

时间限制

1

我的代码：

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

示例输入、输出：

示例 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 算法。看看这个 link 并为每个字母表定义一个前缀和数组。

I am getting time limit error in the competition platform for my code