Dada una string S de longitud N que contiene solo letras en minúsculas, la tarea es imprimir el recuento de substrings de la string dada cuyo anagrama es palindrómico .
Ejemplos:
Entrada: S = “aaaa”
Salida: 10
Explicación:
Las substrings posibles son {“a”, “a”, “a”, “a”, “aa”, “aa”, “aa”, “aaa”, “aaa ”, “aaaa”}. Dado que todas las substrings tienen anagramas palindrómicos, la respuesta requerida es 10.Entrada: S = “abc”
Salida: 3
Enfoque ingenuo: la idea es generar todas las substrings de la string dada y, para cada substring, verificar si su anagrama es un palíndromo o no. Siga aumentando el número de substrings para las que se cumple la condición anterior. Finalmente, imprima el recuento de todas esas substrings.
Complejidad temporal: O(N 3 )
Espacio auxiliar: O(N)
Enfoque de enmascaramiento de bits : la idea es generar las máscaras de números de 26 bits ya que hay 26 caracteres. Además, observe que si el anagrama de alguna string es un palíndromo, entonces las frecuencias de sus caracteres, excepto como máximo un carácter, deben ser pares.
Siga los pasos a continuación para resolver el problema:
- Recorra la string e inicialice una variable X = 0 en cada índice.
- Desde cada i el índice, recorra la string sobre un rango de índices [i, N – 1] , y para cada carácter S[j] , calcule Bitwise XOR de X y 2 (S[j] – ‘a’) , donde El bit 0 representa si la frecuencia de a es impar , el bit 1 representa si la frecuencia de b es impar , y así sucesivamente.
- Luego, verifique si X & (X – 1) es igual a 0 o no. Si se encuentra que es cierto, entonces incremente el conteo en 1 .
Ilustración: suponga que X = (0001000)
2 = > (X – 1) se representará como (0000111) 2 . Por lo tanto, X & (X – 1) = 0
- Una vez agotados los pasos anteriores, imprima el conteo obtenido.
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 print count of substrings
// whose anagrams are palindromic
void countSubstring(string s)
{
// Stores the answer
int res = 0;
// Iterate over the string
for (int i = 0;
i < s.length(); i++) {
int x = 0;
for (int j = i;
j < s.length(); j++) {
// Set the current character
int temp = 1 << s[j] - 'a';
// Parity update
x ^= temp;
if ((x & (x - 1)) == 0)
res++;
}
}
// Print the final count
cout << res;
}
// Driver Code
int main()
{
string str = "aaa";
// Function Call
countSubstring(str);
return 0;
}
Java
// Java program for
// the above approach
class GFG{
// Function to print count of subStrings
// whose anagrams are palindromic
static void countSubString(String s)
{
// Stores the answer
int res = 0;
// Iterate over the String
for (int i = 0; i < s.length(); i++)
{
int x = 0;
for (int j = i; j < s.length(); j++)
{
// Set the current character
int temp = 1 << s.charAt(j) - 'a';
// Parity update
x ^= temp;
if ((x & (x - 1)) == 0)
res++;
}
}
// Print the final count
System.out.print(res);
}
// Driver Code
public static void main(String[] args)
{
String str = "aaa";
// Function Call
countSubString(str);
}
}
// This code is contributed by shikhasingrajput
Python3
# Python3 program for
# the above approach
# Function to print count of subStrings
# whose anagrams are palindromic
def countSubString(s):
# Stores the answer
res = 0;
# Iterate over the String
for i in range(len(s)):
x = 0;
for j in range(i, len(s)):
# Set the current character
temp = 1 << ord(s[j]) - ord('a');
# Parity update
x ^= temp;
if ((x & (x - 1)) == 0):
res += 1;
# Print final count
print(res);
# Driver Code
if __name__ == '__main__':
str = "aaa";
# Function Call
countSubString(str);
# This code is contributed by 29AjayKumar
C#
// C# program for
// the above approach
using System;
class GFG{
// Function to print count of subStrings
// whose anagrams are palindromic
static void countSubString(String s)
{
// Stores the answer
int res = 0;
// Iterate over the String
for (int i = 0; i < s.Length; i++)
{
int x = 0;
for (int j = i; j < s.Length; j++)
{
// Set the current character
int temp = 1 << s[j] - 'a';
// Parity update
x ^= temp;
if ((x & (x - 1)) == 0)
res++;
}
}
// Print the readonly count
Console.Write(res);
}
// Driver Code
public static void Main(String[] args)
{
String str = "aaa";
// Function Call
countSubString(str);
}
}
// This code is contributed by shikhasingrajput
Javascript
<script>
// JavaScript program for
//the above approach
// Function to print count of subStrings
// whose anagrams are palindromic
function countSubString(s)
{
// Stores the answer
let res = 0;
// Iterate over the String
for (let i = 0; i < s.length; i++)
{
let x = 0;
for (let j = i; j < s.length; j++)
{
// Set the current character
let temp = 1 << s[j] - 'a';
// Parity update
x ^= temp;
if ((x & (x - 1)) == 0)
res++;
}
}
// Print the final count
document.write(res);
}
// Driver Code
let str = "aaa";
// Function Call
countSubString(str);
// This code is contributed by souravghosh0416.
</script>
Producción
6
Tiempo Complejidad: O(N 2 )
Espacio Auxiliar: O(N)
Enfoque eficiente: para optimizar la técnica de enmascaramiento de bits anterior , la idea es utilizar un mapa . Siga los pasos a continuación para resolver el problema:
- Inicialice un mapa para almacenar las frecuencias de las máscaras. Inicialice una variable X = 0 .
- Recorra la string y para cada i -ésimo índice, calcule Bitwise XOR de X y 2 (S[j] – ‘a’) y actualice la respuesta agregando la frecuencia del valor actual de X en el Mapa porque si hay alguna substring de 0 to j tiene la misma máscara que la de X , que es una máscara para la substring de 0 a i , entonces la substring S[j + 1, i] tendrá frecuencias pares, donde j < i .
- Sume también las frecuencias de las máscaras X xor 2 k , donde, 0 ≤ k < 26 . Después de eso, incrementa la frecuencia de X en 1 .
- Repita los pasos anteriores para cada índice de la string dada.
- Después de atravesar la string dada, imprima 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 get the count of substrings
// whose anagrams are palindromic
void countSubstring(string s)
{
// Store the answer
int answer = 0;
// Map to store the freq of masks
unordered_map<int, int> m;
// Set frequency for mask
// 00...00 to 1
m[0] = 1;
// Store mask in x from 0 to i
int x = 0;
for (int j = 0; j < s.length(); j++) {
x ^= 1 << (s[j] - 'a');
// Update answer
answer += m[x];
for (int i = 0; i < 26; ++i) {
answer += m[x ^ (1 << i)];
}
// Update frequency
m[x] += 1;
}
// Print the answer
cout << answer;
}
// Driver Code
int main()
{
string str = "abab";
// Function Call
countSubstring(str);
return 0;
}
Java
// Java program for
// the above approach
import java.util.*;
class GFG {
// Function to get the count of subStrings
// whose anagrams are palindromic
static void countSubString(String s)
{
// Store the answer
int answer = 0;
// Map to store the freq of masks
HashMap<Integer,
Integer> m = new HashMap<Integer,
Integer>();
// Set frequency for mask
// 00...00 to 1
m.put(0, 1);
// Store mask in x from 0 to i
int x = 0;
for (int j = 0; j < s.length(); j++)
{
x ^= 1 << (s.charAt(j) - 'a');
// Update answer
answer += m.containsKey(x) ? m.get(x) : 0;
for (int i = 0; i < 26; ++i)
{
answer += m.containsKey(x ^ (1 << i)) ?
m.get(x ^ (1 << i)) : 0;
}
// Update frequency
if (m.containsKey(x))
m.put(x, m.get(x) + 1);
else
m.put(x, 1);
}
// Print the answer
System.out.print(answer);
}
// Driver Code
public static void main(String[] args)
{
String str = "abab";
// Function Call
countSubString(str);
}
}
// This code is contributed by shikhasingrajput
Python3
# Python3 program for the above approach
from collections import defaultdict
# Function to get the count of substrings
# whose anagrams are palindromic
def countSubstring(s):
# Store the answer
answer = 0
# Map to store the freq of masks
m = defaultdict(lambda : 0)
# Set frequency for mask
# 00...00 to 1
m[0] = 1
# Store mask in x from 0 to i
x = 0
for j in range(len(s)):
x ^= 1 << (ord(s[j]) - ord('a'))
# Update answer
answer += m[x]
for i in range(26):
answer += m[x ^ (1 << i)]
# Update frequency
m[x] += 1
# Print the answer
print(answer)
# Driver Code
str = "abab"
# Function call
countSubstring(str)
# This code is contributed by Shivam Singh
C#
// C# program for
// the above approach
using System;
using System.Collections.Generic;
class GFG{
// Function to get the count of
// subStrings whose anagrams
// are palindromic
static void countSubString(String s)
{
// Store the answer
int answer = 0;
// Map to store the freq of masks
Dictionary<int,
int> m = new Dictionary<int,
int>();
// Set frequency for mask
// 00...00 to 1
m.Add(0, 1);
// Store mask in x from 0 to i
int x = 0;
for (int j = 0; j < s.Length; j++)
{
x ^= 1 << (s[j] - 'a');
// Update answer
answer += m.ContainsKey(x) ? m[x] : 0;
for (int i = 0; i < 26; ++i)
{
answer += m.ContainsKey(x ^ (1 << i)) ?
m[x ^ (1 << i)] : 0;
}
// Update frequency
if (m.ContainsKey(x))
m[x] = m[x] + 1;
else
m.Add(x, 1);
}
// Print the answer
Console.Write(answer);
}
// Driver Code
public static void Main(String[] args)
{
String str = "abab";
// Function Call
countSubString(str);
}
}
// This code is contributed by shikhasingrajput
Javascript
<script>
// JavaScript program for the above approach
// Function to get the count of substrings
// whose anagrams are palindromic
function countSubstring(s)
{
// Store the answer
var answer = 0;
// Map to store the freq of masks
var m = new Map();
// Set frequency for mask
// 00...00 to 1
m.set(0, 1);
// Store mask in x from 0 to i
var x = 0;
for (var j = 0; j < s.length; j++) {
x ^= 1 << (s[j].charCodeAt(0) - 'a'.charCodeAt(0));
// Update answer
answer += m.has(x)? m.get(x):0;
for (var i = 0; i < 26; ++i) {
answer += m.has(x ^ (1 << i))?m.get(x ^ (1 << i)):0;
}
// Update frequency
if(m.has(x))
m.set(x, m.get(x)+1)
else
m.set(x, 1)
}
// Print the answer
document.write( answer);
}
// Driver Code
var str = "abab";
// Function Call
countSubstring(str);
</script>
Producción
7
Complejidad temporal: O(N)
Espacio auxiliar: O(N)
Publicación traducida automáticamente
Artículo escrito por gdgokhulan0 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA