范围内最常见的角色

Question

我有一串s长度n.什么是最有效的数据结构/算法用于查找范围内最常见的字符i..j？

该字符串不随时间而改变,我只需要重复问其中最常见的字符查询s[i],s[i + 1]..., s[j].

Answer 1

一个数组,其中包含每个字符的出现次数.在迭代字符串一次时增加相应的值.在执行此操作时,您可以记住数组中的当前最大值; 或者,在最后查找数组中的最高值.

伪代码

arr = [0]
for ( char in string )
   arr[char]++
mostFrequent = highest(arr)