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

Question

我正在尝试使用以下代码在在线编码平台(下面给出的问题(中解决此问题。比赛平台显示时间限制错误。

问题：

Tahir和Mamta正在TCS的一个项目中醒来。塔希尔是一个问题解决者，他为他的朋友Mamta提出了一个有趣的问题。

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

接下来是 Q 查询，其中每个查询将包含一个整数 P (1<=P<=N(，表示字符串中的位置。

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

玛姆塔忙于她的办公室工作。因此，她请你帮助她。

约束

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

阿巴克斯达

阿拉伯数字

9

3

输出

3

1

解释

这里 Q = 2

对于 P=9，第 9 个位置的字符为"a"。在 P 之前出现"a"的次数，即 9 是 3。

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

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

Answer 1

解决方案的复杂性为 O(n²(，它会导致时间限制错误。 您应该使用prefix sum array算法。查看此链接并为每个字母表定义一个前缀总和数组。