Tahir and Mamta are working in a project in TCS. Tahir being a problem solver came up with an interesting problem for his friend Mamta.
The 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 the 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.
Output
For each query, print an integer denoting the answer on single line.
Test Case
Explanation
Example 1
Input
9
abacsddaa
2
9
3
Output
3
1
Explanation
Here Q = 2
For P=9, character at 9th location is 'a'. Number of occurrences of 'a' before P i.e., 9 is three.
Similarly for P=3, 3rd character is 'a'. Number of occurrences of 'a' before P. i.e., 3 is one.
Answers
Answer:
#include <iostream>
#include <string>
using namespace std;
void count1(string s, int c[], int n)
{
int res, a;
for (int i = 0; i < n ; i++)
{
res = 0;
a = c[i];
char temp = s[a-1];
for(int j = 0; j < a-1; j++)
{
if (s[j] == temp)
res++;
}
cout<<res<<endl;
}
}
int main()
{
unsigned int len;
unsigned short int quer;
string str;
cin>>len;
cin>>str;
cin>>quer;
int querry[quer];
for (int i = 0; i < quer; i++)
{
cin>>querry[i];
}
count1(str, querry, quer);
return 0;
}
Explanation:
Please do not copy as I am also attending Codevita exam. Understand the logic by looking at this program. If found copied, we both will be disqualified.
n=int(input())
s=input()
q=int(input())
for i in range(q):
p=int(input())
temp=s[p-1]
d=s[0:p-1]
x=d.count(temp)
print(x)