I want to find the occurrences of a character in a string for n queries: For example the string is: "i_love_mathematics" and the task is to find the occurrence of:
'i' in range:
1-4(a substring starting from 1st character and ending at 4th)
2-5
3-10
'_' in range:
1-10
3-9
The output would be:
1
0
0
2
1
The similar question was to find the number of occurrences of a character in a string but the complexity for that was O(N) but in this case, if I do that it would result in very high complexity, is there a data structure that could be used to solve this problem?
We will keep the number of occurrences of each character at each position, for example the string abacaba
a b a c a b a
| |1|2|3|4|5|6|7
a | 1 1 2 2 3 3 4
b | 0 1 1 1 1 2 2
c | 0 0 0 1 1 1 1
Now, if we want to answer a query we do the following
Letter 'a' in range 3-5
We do a at position 5 minus number of occurrences before position 3, that is a[5]-a[3-1]=3-1=2 there are 2 occurrences of the letter 'a' in range 3 to 5