Question

Tahir and Mamta are woking in a project in TCS. Tahir being a problem solver came up with an interesting problem for his friend Mamta.

Problem consists of a string of length N and contains only small case alphabets.

It will be followed by Q queries, in which each query will contain an integer P (1<=P<=N) denoting a position within the string.

Mamta's task is to find the alphabet present at that location and determine the number of occurrence of same alphabet preceding the given location P.

Mamta is busy with her office work. Therefore, she asked you to help her.

Constraints
1 <= N <= 500000

S consisting of small case alphabets

1 <= Q <= 10000

1 <= P <= N

Input Format
First line contains an integer N, denoting the length of string.

Second line contains string S itself consists of small case alphabets only ('a' - 'z').

Third line contains an integer Q denoting number of queries that will be asked.

Next Q lines contains an integer P (1 <= P <= N) for which you need to find the number occurrence of character present at the Pth location preceeding P.

Answer 1

Substring Counter

We will be using Python 3. It will make our code very short and simple.

So, we have the string S, its length N and number of queries Q.

For each query, we get a position P.

We just need to count number of occurrences of alphabet at P preceding that position. For this, we will use the very simple count() function in Python.

str.count(substring, start, end)

This method returns the number of occurrences of the substring in str from the start index to the end index. [end index excluded]

Just by using this simple function, we can get the answer.

$\rule{320}{1}$

Program Code: SubstringCounter.py

N = int(input())    # Length of string S

S = input()         # String S

Q = int(input())    # Number of Queries

for i in range(Q):

   P = int(input())    # Location of alphabet in query

   # Count the letter S[P-1] from

   # 0 to P-1 (P-1 excluded)

   print(S.count(S[P-1], 0, P-1))