Dada una string S de longitud N que contiene solo letras minúsculas. Además, dadas Q consultas donde cada consulta consta de un entero P tal que 1≤ P ≤ N . La tarea es encontrar el recuento de ocurrencias de la misma letra que precede a la ubicación P dada .
Ejemplos:
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.
Enfoque ingenuo Para cada consulta Q i que da la posición ‘p’, ejecute un ciclo de 1 a ‘p-1’ y verifique si el elemento presente en ese índice es igual al elemento en el índice ‘p’, si es cierto que aumente el valor de la variable de contador por 1. Después de completar el bucle, imprima el valor de la variable de contador en una nueva línea.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation of the approach
#include<bits/stdc++.h>
using namespace std;
int Count(string s, int pos )
{
// returns character at index pos - 1
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;
}
// Driver Code
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;
}
// This code is contributed by
// divyamohan123
Java
// Java implementation of the approach
class GFG
{
static int Count(String s, int pos )
{
// returns character at index pos - 1
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;
}
// Driver Code
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));
}
}
}
// This code is contributed by AnkitRai01
Python3
# Python 3 implementation of the approach def Count( s, pos ): # returns character at index pos - 1 c = s[pos - 1] counter = 0 for i in range( pos - 1 ): if s[i] == c: counter = counter + 1 return counter # Driver Code 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#
// C# implementation of the approach
using System;
class GFG
{
static int Count(String s, int pos )
{
// returns character at index pos - 1
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;
}
// Driver Code
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));
}
}
}
// This code is contributed by 29AjayKumar
Javascript
<script>
// Javascript implementation of the approach
function Count(s, pos )
{
// returns character at index pos - 1
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;
}
// Driver code
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/>");
}
// This code is contributed by susmitakundugoaldanga.
</script>
Producción:
3 1 0
Complejidad de tiempo: O(N)
Complejidad de espacio: O(1)
Mejor enfoque: Usar Hashing o Diccionario y espacio auxiliar.
Cree una array auxiliar y diga ‘temp’, que se inicializa en cero y la tabla hash o el diccionario ‘d’
inicialmente vacío. Para fines de preprocesamiento, es decir, almacenar el recuento anterior de elementos en el índice ‘pos’ en el índice pos en 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;
Coloca todo el valor requerido en el índice respectivo de la array auxiliar. Para cada consulta Q imprimo val en la posición ‘pos’ en temp.
C++
// C++ implementation of the approach
#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;
}
// Driver Code
int main()
{
string s = "abacsddaa";
int n = s.length();
vector<int> temp = processing(s, n);
Count(temp);
}
// This code is contributed
// by Surendra_Gangwar
Java
// Java implementation of the approach
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;
}
// Driver Code
public static void main(String[] args)
{
String s = "abacsddaa";
int n = s.length();
int[] temp = processing(s, n);
Count(temp);
}
}
// This code is contributed by Rajput-Ji
Python3
# Python 3 implementation of the approach 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 # Driver Code if __name__ == "__main__" : s = "abacsddaa" n = len(s) temp = processing( s ) Count( temp )
C#
// C# implementation of the approach
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;
}
// Driver Code
public static void Main(String[] args)
{
String s = "abacsddaa";
int n = s.Length;
int[] temp = processing(s, n);
Count(temp);
}
}
// This code is contributed by PrinciRaj1992
Producción:
3 1 0
Complejidad de tiempo: O(N)
Publicación traducida automáticamente
Artículo escrito por Kaushal_Agarwal y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA