TCS Codevita | Similar Character

In this blog, we will discuss a problem asked in TCS Codevita 2019.

Before running into the solution please solve it by yourself.

Problem Description:

Tahir and Mamta are working on 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 occurrences 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 the string.

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

The third line contains an integer Q denoting the number of queries that will be asked.

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

Output:

For each query, print an integer denoting the answer on a single line.

Time Limit:

1

Example 1:

Input:

9
abacsddaa
2
9
3

Output:

3
1

Explanation:

Here Q = 2

For P=9, the character at the 9th location is 'a'. The number of occurrences of 'a' before P i.e., 9 is three.

Similarly, for P=3, 3rd character is 'a'. The number of occurrences of 'a' before P. i.e., 3 is one.

---

Implementation using 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;
}

---

Happy Coding!

Follow us on Instagram @programmersdoor

Join us on Telegram @programmersdoor

Please write comments if you find any bug in the above code/algorithm, or find other ways to solve the same problem.

Follow Programmers Door for more.

#blog #interview #placement #learn #computer #science