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 occurrences of same alphabet preceding the given location P. Mamta is busy with her office work. Therefore, she asked you to help her.
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 Format:
For each query, print an integer denoting the answer on single line.
Constraints:
• 1 <= N <= 500000
• S consisting of small case alphabets
• 1 <= Q <= 10000
• 1 <= P <= N
Example 1
Input:
9
abacsddaa
2
9
3
Output:
3
1
Solution: In C
#include <stdio.h>
#include <string.h>
int main()
{
int n;
scanf("%d", &n);
char str[n];
scanf("%s", &str);
int q;
scanf("%d", &q);
int qlines[q];
for(int i = 0; i<q; i++)
{
scanf("%d",&qlines[i]);
}
int counter[q];
int result;
for(int j = 0; j<q; j++) //how many times we have to iterate
{
int count1=0;
int p=qlines[j]-1; //
char r=str[p]; //char at pth position copied at char r
for(int k = 0; k<qlines[j]-1; k++)
{
if(str[k] == r) //for comparing char
{
count1++;
}
}
counter[j]=count1; //no of occurence stored at jth position
}
for(int i = 0; i<q; i++)
printf("%d\n", counter[i]);
return 0;
}Solution: In Java
import java.util.*;
class Main{
public static void main(String[] args){
Scanner ip=new Scanner(System.in);
int n;
n=ip.nextInt();
char[] str=ip.next().toCharArray();
int q;
q=ip.nextInt();
int[] qlines=new int[q];
for(int i = 0; i<q; i++)
{
qlines[i]=ip.nextInt();
}
int[] counter=new int[q];
int result;
for(int j = 0; j<q; j++)
{
int count1=0;
int p=qlines[j]-1;
char r=str[p];
for(int k = 0; k<qlines[j]-1; k++)
{
if(str[k] == r)
{
count1++;
}
}
counter[j]=count1;
}
for(int i = 0; i<q; i++)
System.out.printf("%d\n", counter[i]);
}
}Also Checkout