Given a string S of length N containing only lowercase letters. Also, given Q queries where each query consists of an integer P such that 1? P ? N. The task is to find the count of occurrences of the same letter preceding the given location P.
Input: S = "abacsddaa", Q[] = {9, 3}
Output:
3
1
For first query, P = 9, character at 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.
Naive approach For each query Qi which gives position ‘p’, run a loop from 1 to ‘p-1’ and check whether element present at that index is equal to element at index ‘p’, if it is true then increase the value of counter variable 1. After completion of loop print the value of the counter variable in a new line.
Below is the implementation of the above approach:
C++
#include<bits/stdc++.h>
using namespace std;
int Count(string s, int pos )
{
int c = s[pos - 1] ;
int counter = 0 ;
for ( int i = 0; i < pos-1; i++ )
{
if (s[i] == c)
counter = counter + 1;
}
return counter;
}
int main()
{
string s = "abacsddaa" ;
int pos;
int n = s.length();
int query[] = {9, 3, 2};
int Q = sizeof (query) / sizeof (query[0]);
for ( int i = 0; i < Q; i++ )
{
pos = query[i] ;
cout << Count( s, pos ) << endl;
}
return 0;
}
|
Java
class GFG
{
static int Count(String s, int pos )
{
int c = s.charAt(pos - 1 );
int counter = 0 ;
for ( int i = 0 ; i < pos - 1 ; i++ )
{
if (s.charAt(i) == c)
counter = counter + 1 ;
}
return counter;
}
public static void main (String[] args)
{
String s = "abacsddaa" ;
int pos;
int n = s.length();
int query[] = { 9 , 3 , 2 };
int Q = query.length;
for ( int i = 0 ; i < Q; i++)
{
pos = query[i];
System.out.println(Count(s, pos));
}
}
}
|
Python3
def Count( s, pos ):
c = s[pos - 1 ]
counter = 0
for i in range ( pos - 1 ):
if s[i] = = c:
counter = counter + 1
return counter
if __name__ = = "__main__" :
s = "abacsddaa"
n = len (s)
query = [ 9 , 3 , 2 ]
Q = len (query)
for i in range ( Q ):
pos = query[i]
print (Count( s, pos ))
|
C#
using System;
class GFG
{
static int Count(String s, int pos )
{
int c = s[pos - 1];
int counter = 0;
for ( int i = 0; i < pos - 1; i++ )
{
if (s[i] == c)
counter = counter + 1;
}
return counter;
}
public static void Main (String[] args)
{
String s = "abacsddaa" ;
int pos;
int n = s.Length;
int []query = {9, 3, 2};
int Q = query.Length;
for ( int i = 0; i < Q; i++)
{
pos = query[i];
Console.WriteLine(Count(s, pos));
}
}
}
|
Javascript
<script>
function Count(s, pos )
{
let c = s[pos - 1];
let counter = 0;
for (let i = 0; i < pos - 1; i++ )
{
if (s[i] == c)
counter = counter + 1;
}
return counter;
}
let s = "abacsddaa" ;
let pos;
let n = s.length;
let query = [9, 3, 2];
let Q = query.length;
for (let i = 0; i < Q; i++)
{
pos = query[i];
document.write(Count(s, pos) + "<br/>" );
}
</script>
|
Time Complexity: O(N)
Auxiliary Space: O(1)
Better approach: Using Hashing or Dictionary and auxiliary space.
Create an auxiliary array say ‘temp’ which initialize to zero and hash table or dictionary ‘d’
initially empty. For pre-processing purposes, that is to store the previous count of elements at index ‘pos’ at index pos in temp.
Preprocessing function
Pseudo Code:
function Preprocess(s):
for i=1 to length(s),
if s(i) not in hash_table,
hash_table(s(i)) := i,
end;
else,
auxiliary_array(i) = hash_table(s(i)) + 1,
hash_table(s(i)) = i,
end;
It place all the required value at respective index of auxiliary array. For each query Qi print val at position ‘pos’ in temp.
C++
#include<bits/stdc++.h>
using namespace std;
void Count(vector< int > temp)
{
int query[] = {9, 3, 2};
int Q = sizeof (query) /
sizeof (query[0]);
for ( int i = 0; i < Q; i++)
{
int pos = query[i];
cout << (temp[pos - 1]) << endl;
}
}
vector< int > processing(string s, int len)
{
vector< int > temp(len);
map< char , int > d;
for ( int i = 0; i < len; i++)
{
if (d.find(s[i]) == d.end())
{
d[s[i]] = i;
}
else
{
temp[i] = temp[d[s[i]]] + 1;
d[s[i]] = i;
}
}
return temp;
}
int main()
{
string s = "abacsddaa" ;
int n = s.length();
vector< int > temp = processing(s, n);
Count(temp);
}
|
Java
import java.util.*;
class GFG
{
static void Count( int [] temp)
{
int [] query = { 9 , 3 , 2 };
int Q = query.length;
for ( int i = 0 ; i < Q; i++)
{
int pos = query[i];
System.out.println(temp[pos - 1 ]);
}
}
static int [] processing(String s, int len)
{
int [] temp = new int [len];
HashMap<Character,
Integer> d = new HashMap<Character,
Integer>();
for ( int i = 0 ; i < len; i++)
{
if (!d.containsKey(s.charAt(i)))
{
d.put(s.charAt(i), i);
}
else
{
temp[i] = temp[d.get(s.charAt(i))] + 1 ;
d.put(s.charAt(i), i);
}
}
return temp;
}
public static void main(String[] args)
{
String s = "abacsddaa" ;
int n = s.length();
int [] temp = processing(s, n);
Count(temp);
}
}
|
Python3
def Count( temp ):
query = [ 9 , 3 , 2 ]
Q = len (query)
for i in range ( Q ):
pos = query[i]
print ( temp[pos - 1 ] )
def processing( s ):
temp = [ 0 ] * len ( s )
d = dict ( )
for i in range ( len ( s ) ):
if s[i] not in d:
d[ s[i] ] = i
else :
temp[i] = temp[ d[ s[i] ] ] + 1
d[ s[i] ] = i
return temp
if __name__ = = "__main__" :
s = "abacsddaa"
n = len (s)
temp = processing( s )
Count( temp )
|
C#
using System;
using System.Collections.Generic;
class GFG
{
static void Count( int [] temp)
{
int [] query = {9, 3, 2};
int Q = query.Length;
for ( int i = 0; i < Q; i++)
{
int pos = query[i];
Console.WriteLine(temp[pos - 1]);
}
}
static int [] processing(String s, int len)
{
int [] temp = new int [len];
Dictionary< int ,
int > d = new Dictionary< int ,
int >();
for ( int i = 0; i < len; i++)
{
if (!d.ContainsKey(s[i]))
{
d.Add(s[i], i);
}
else
{
temp[i] = temp[d[s[i]]] + 1;
d[s[i]] = i;
}
}
return temp;
}
public static void Main(String[] args)
{
String s = "abacsddaa" ;
int n = s.Length;
int [] temp = processing(s, n);
Count(temp);
}
}
|
Javascript
const Count = (temp) => {
const query = [9, 3, 2];
const Q = query.length;
for (let i = 0; i < Q; i++) {
const pos = query[i];
console.log(temp[pos - 1]);
}
};
const processing = (s, len) => {
const temp = Array(len).fill(0);
const d = new Map();
for (let i = 0; i < len; i++) {
if (!d.has(s[i])) {
d.set(s[i], i);
} else {
temp[i] = temp[d.get(s[i])] + 1;
d.set(s[i], i);
}
}
return temp;
};
const s = "abacsddaa" ;
const n = s.length;
const temp = processing(s, n);
Count(temp);
|
Time Complexity: O(N), where N is the length of the given string.
Auxiliary Space: O(N)
Contact Us