Dada una string S de longitud N , que consiste en letras minúsculas y consultas Q[][] de la forma [L, R], la tarea es contar el número de caracteres que aparecen un número impar de veces en el rango [L ,R].
Ejemplos:
Entrada: S = “geeksforgeeks”, Q[][] = {{2, 4}, {0, 3}, {0, 12}}
Salida: 3 2 3
Explicación:
los caracteres aparecen un número impar de veces en [2, 4]: {‘e’, ‘k’, ‘s’}.
Caracteres que aparecen un número impar de veces en [0, 3]: {‘g’, ‘k’}.
Caracteres que aparecen un número impar de veces en [0, 12]: {‘f’, ‘o’, ‘r’}.Entrada: S = “hola”, Q[][] = {{0, 4}}
Salida: 3
Explicación: Caracteres que aparecen un número impar de veces en [0, 4]: {‘h’, ‘e’, ’o ‘}.
Acercarse :
Siga los pasos a continuación para resolver el problema:
- Cada personaje se puede representar con una potencia única de dos (en orden ascendente). Por ejemplo, 2 0 para ‘a’ , 2 1 para ‘b’ y así sucesivamente, hasta 2 25 para ‘z’ .
- Inicialice una array arr[] de tamaño N donde arr[i] es el valor entero correspondiente de S[i] .
- Construya una array de prefijos prefijo[] de tamaño N donde prefijo[i] es el valor de la operación XOR realizada en todos los números desde arr[0] hasta arr[i] .
- El número de bits establecidos en el valor XOR de {arr[L], arr[L + 1], …, arr[R – 1], arr[R]} da la respuesta requerida para el rango dado [L, R] .
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ Program to implement
// the above problem
#include <bits/stdc++.h>
using namespace std;
// Function to print the number
// of characters having odd
// frequencies for each query
void queryResult(int prefix[],
pair<int, int> Q)
{
int l = Q.first;
int r = Q.second;
if (l == 0) {
int xorval = prefix[r];
cout << __builtin_popcount(xorval)
<< endl;
}
else {
int xorval = prefix[r]
^ prefix[l - 1];
cout << __builtin_popcount(xorval)
<< endl;
}
}
// A function to construct
// the arr[] and prefix[]
void calculateCount(string S,
pair<int, int> Q[],
int m)
{
// Stores array length
int n = S.length();
// Stores the unique powers of 2
// associated to each character
int arr[n];
for (int i = 0; i < n; i++) {
arr[i] = (1 << (S[i] - 'a'));
}
// Prefix array to store the
// XOR values from array elements
int prefix[n];
int x = 0;
for (int i = 0; i < n; i++) {
x ^= arr[i];
prefix[i] = x;
}
for (int i = 0; i < m; i++) {
queryResult(prefix, Q[i]);
}
}
// Driver Code
int main()
{
string S = "geeksforgeeks";
pair<int, int> Q[] = { { 2, 4 },
{ 0, 3 },
{ 0, 12 } };
calculateCount(S, Q, 3);
}
Java
// Java Program to implement
// the above problem
import java.util.*;
class GFG{
static class pair
{
int first, second;
public pair(int first, int second)
{
this.first = first;
this.second = second;
}
}
// Function to print the number
// of characters having odd
// frequencies for each query
static void queryResult(int prefix[], pair Q)
{
int l = Q.first;
int r = Q.second;
if (l == 0)
{
int xorval = prefix[r];
System.out.print(Integer.bitCount(xorval) + "\n");
}
else
{
int xorval = prefix[r] ^ prefix[l - 1];
System.out.print(Integer.bitCount(xorval) + "\n");
}
}
// A function to construct
// the arr[] and prefix[]
static void calculateCount(String S, pair Q[], int m)
{
// Stores array length
int n = S.length();
// Stores the unique powers of 2
// associated to each character
int[] arr = new int[n];
for (int i = 0; i < n; i++)
{
arr[i] = (1 << (S.charAt(i) - 'a'));
}
// Prefix array to store the
// XOR values from array elements
int[] prefix = new int[n];
int x = 0;
for (int i = 0; i < n; i++)
{
x ^= arr[i];
prefix[i] = x;
}
for (int i = 0; i < m; i++)
{
queryResult(prefix, Q[i]);
}
}
// Driver Code
public static void main(String[] args)
{
String S = "geeksforgeeks";
pair Q[] = {new pair(2, 4),
new pair(0, 3), new pair(0, 12)};
calculateCount(S, Q, 3);
}
}
// This code is contributed by shikhasingrajput
Python3
# Python3 program to implement
# the above approach
# Function to print the number
# of characters having odd
# frequencies for each query
def queryResult(prefix, Q):
l = Q[0]
r = Q[1]
if(l == 0):
xorval = prefix[r]
print(bin(xorval).count('1'))
else:
xorval = prefix[r] ^ prefix[l - 1]
print(bin(xorval).count('1'))
# A function to construct
# the arr[] and prefix[]
def calculateCount(S, Q, m):
# Stores array length
n = len(S)
# Stores the unique powers of 2
# associated to each character
arr = [0] * n
for i in range(n):
arr[i] = (1 << (ord(S[i]) - ord('a')))
# Prefix array to store the
# XOR values from array elements
prefix = [0] * n
x = 0
for i in range(n):
x ^= arr[i]
prefix[i] = x
for i in range(m):
queryResult(prefix, Q[i])
# Driver Code
if __name__ == '__main__':
S = "geeksforgeeks"
# Function call
Q = [ [ 2, 4 ],
[ 0, 3 ],
[ 0, 12 ] ]
calculateCount(S, Q, 3)
# This code is contributed by Shivam Singh
C#
// C# program to implement
// the above problem
using System;
class GFG{
class pair
{
public int first, second;
public pair(int first, int second)
{
this.first = first;
this.second = second;
}
}
// Function to print the number
// of characters having odd
// frequencies for each query
static void queryResult(int []prefix, pair Q)
{
int l = Q.first;
int r = Q.second;
if (l == 0)
{
int xorval = prefix[r];
Console.Write(countSetBits(xorval) + "\n");
}
else
{
int xorval = prefix[r] ^ prefix[l - 1];
Console.Write(countSetBits(xorval) + "\n");
}
}
// A function to construct
// the []arr and prefix[]
static void calculateCount(String S, pair []Q,
int m)
{
// Stores array length
int n = S.Length;
// Stores the unique powers of 2
// associated to each character
int[] arr = new int[n];
for(int i = 0; i < n; i++)
{
arr[i] = (1 << (S[i] - 'a'));
}
// Prefix array to store the
// XOR values from array elements
int[] prefix = new int[n];
int x = 0;
for(int i = 0; i < n; i++)
{
x ^= arr[i];
prefix[i] = x;
}
for(int i = 0; i < m; i++)
{
queryResult(prefix, Q[i]);
}
}
static int countSetBits(long x)
{
int setBits = 0;
while (x != 0)
{
x = x & (x - 1);
setBits++;
}
return setBits;
}
// Driver Code
public static void Main(String[] args)
{
String S = "geeksforgeeks";
pair []Q = { new pair(2, 4),
new pair(0, 3),
new pair(0, 12) };
calculateCount(S, Q, 3);
}
}
// This code is contributed by Amit Katiyar
Javascript
<script>
// Javascript program to implement the above problem
// Function to print the number
// of characters having odd
// frequencies for each query
function queryResult(prefix, Q)
{
let l = Q[0];
let r = Q[1];
if (l == 0)
{
let xorval = prefix[r];
document.write(countSetBits(xorval) + "</br>");
}
else
{
let xorval = prefix[r] ^ prefix[l - 1];
document.write(countSetBits(xorval) + "</br>");
}
}
// A function to construct
// the []arr and prefix[]
function calculateCount(S, Q, m)
{
// Stores array length
let n = S.length;
// Stores the unique powers of 2
// associated to each character
let arr = new Array(n);
for(let i = 0; i < n; i++)
{
arr[i] = (1 << (S[i].charCodeAt() - 'a'.charCodeAt()));
}
// Prefix array to store the
// XOR values from array elements
let prefix = new Array(n);
let x = 0;
for(let i = 0; i < n; i++)
{
x ^= arr[i];
prefix[i] = x;
}
for(let i = 0; i < m; i++)
{
queryResult(prefix, Q[i]);
}
}
function countSetBits(x)
{
let setBits = 0;
while (x != 0)
{
x = x & (x - 1);
setBits++;
}
return setBits;
}
let S = "geeksforgeeks";
let Q = [ [2, 4], [0, 3], [0, 12] ];
calculateCount(S, Q, 3);
</script>
Producción:
3 2 3
Complejidad temporal: O(N + Q)
Espacio auxiliar: O(N)
Publicación traducida automáticamente
Artículo escrito por DiptayanBiswas y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA