Dada una string S de N caracteres, la tarea es calcular el número total de substrings no vacías de modo que, como máximo, un carácter aparezca un número impar de veces.
Ejemplo :
Entrada : S = “aba”
Salida : 4
Explicación : Las substrings válidas son “a”, “b”, “a” y “aba”. Por lo tanto, el número total de substrings requeridas es 4.Entrada : “aabb”
Salida : 9
Explicación : Las substrings válidas son “a”, “aa”, “aab”, “aabb”, “a”, “abb”, “b”, “bb” y “b” .
Enfoque : El problema anterior se puede resolver con la ayuda de Bit Masking usando HashMaps . Siga los pasos mencionados a continuación para resolver el problema:
- La paridad de la frecuencia de cada carácter se puede almacenar en una máscara de bits , donde el i -ésimo carácter está representado por 2i . Inicialmente el valor de mask = 0 .
- Crea un mapa desordenado visto , que almacena la frecuencia de aparición de cada máscara de bits. Inicialmente, el valor de seen[0] = 1 .
- Cree una variable cnt , que almacene el recuento de las substrings válidas. Inicialmente, el valor de cnt = 0 .
- Iterar para cada i en el rango [0, N) y Bitwise XOR el valor de la máscara con el número entero que representa el i -ésimo carácter de la string e incrementar el valor de cnt por seen[mask] .
- Para cada i válido , itere a través de todos los caracteres en el rango [a, z] y aumente su frecuencia cambiando el j – ésimo conjunto de bits en la máscara actual e incrementando el valor del cnt por la frecuencia de la máscara de bits después de cambiar el j -ésimo conjunto de bits.
- El valor almacenado en cnt es la respuesta requerida.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to find the count of substrings
// such that at most one character occurs
// odd number of times
int uniqueSubstrings(string S)
{
// Stores the frequency of the bitmasks
unordered_map<int, int> seen;
// Initial Condition
seen[0] = 1;
// Store the current value of the bitmask
int mask = 0;
// Stores the total count of the
// valid substrings
int cnt = 0;
for (int i = 0; i < S.length(); ++i) {
// XOR the mask with current character
mask ^= (1 << (S[i] - 'a'));
// Increment the count by mask count
// of strings with all even frequencies
cnt += seen[mask];
for (int j = 0; j < 26; ++j) {
// Increment count by mask count
// of strings if exist with the
// jth character having odd frequency
cnt += seen[mask ^ (1 << j)];
}
seen[mask]++;
}
// Return Answer
return cnt;
}
// Driver Code
int main()
{
string word = "aabb";
cout << uniqueSubstrings(word);
return 0;
}
Python3
# Python program for the above approach
# Function to find the count of substrings
# such that at most one character occurs
# odd number of times
def uniqueSubstrings(S):
# Stores the frequency of the bitmasks
seen = {}
# Initial Condition
seen[0] = 1
# Store the current value of the bitmask
mask = 0
# Stores the total count of the
# valid substrings
cnt = 0
for i in range(len(S)):
# XOR the mask with current character
mask ^= (1 << (ord(S[i]) - ord('a')))
# Increment the count by mask count
# of strings with all even frequencies
if mask in seen:
cnt += seen[mask]
else:
cnt += 0
for j in range(26):
# Increment count by mask count
# of strings if exist with the
# jth character having odd frequency
if mask ^ (1 << j) in seen:
cnt += seen[mask ^ (1 << j)]
else:
cnt += 0
if mask in seen:
seen[mask] += 1
else:
seen[mask] = 1
# Return Answer
return cnt
# Driver Code
word = "aabb"
print(uniqueSubstrings(word))
# This code is contributed by rj13to.
C#
// C# program for the above approach
using System;
using System.Collections.Generic;
class GFG{
// Function to find the count of substrings
// such that at most one character occurs
// odd number of times
static int uniqueSubstrings(string S)
{
// Stores the frequency of the bitmasks
Dictionary<int,
int> seen = new Dictionary<int,
int>();
// Initial Condition
seen[0] = 1;
// Store the current value of the bitmask
int mask = 0;
// Stores the total count of the
// valid substrings
int cnt = 0;
for(int i = 0; i < S.Length; ++i)
{
// XOR the mask with current character
mask ^= (1 << (S[i] - 'a'));
// Increment the count by mask count
// of strings with all even frequencies
if (seen.ContainsKey(mask))
cnt += seen[mask];
for(int j = 0; j < 26; ++j)
{
// Increment count by mask count
// of strings if exist with the
// jth character having odd frequency
if (seen.ContainsKey(mask ^ (1 << j)))
cnt += seen[mask ^ (1 << j)];
}
if (seen.ContainsKey(mask))
seen[mask]++;
else
seen[mask] = 1;
}
// Return Answer
return cnt;
}
// Driver Code
public static void Main()
{
string word = "aabb";
Console.WriteLine(uniqueSubstrings(word));
}
}
// This code is contributed by ukasp
Javascript
<script>
// Javascript program for the above approach
// Function to find the count of substrings
// such that at most one character occurs
// odd number of times
function uniqueSubstrings(S)
{
// Stores the frequency of the bitmasks
let seen = new Map();
// Initial Condition
seen.set(0, 1);
// Store the current value of the bitmask
let mask = 0;
// Stores the total count of the
// valid substrings
let cnt = 0;
for(let i = 0; i < S.length; ++i)
{
// XOR the mask with current character
mask ^= (1 << (S[i].charCodeAt(0) - 'a'.charCodeAt(0)));
// Increment the count by mask count
// of strings with all even frequencies
if (seen.has(mask))
cnt += seen.get(mask);
for(let j = 0; j < 26; ++j)
{
// Increment count by mask count
// of strings if exist with the
// jth character having odd frequency
if (seen.has(mask ^ (1 << j)))
cnt += seen.get(mask ^ (1 << j));
}
if (seen.has(mask))
seen.set(mask, seen.get(mask) + 1);
else
seen.set(mask, 1);
}
// Return Answer
return cnt;
}
// Driver Code
let word = "aabb";
document.write(uniqueSubstrings(word));
// This code is contributed by Saurabh Jaiswal
</script>
Producción:
9
Tiempo Complejidad : O(N)
Espacio Auxiliar : O(N)
Publicación traducida automáticamente
Artículo escrito por kartikmodi y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA