Número total de substrings de anagramas

Dada una string de caracteres del alfabeto inferior, cuente la substring total de esta string que son anagramas entre sí.

Ejemplos:

Input  : str = “xyyx”
Output : 4
Total substrings of this string which
are anagram to each other are 4 which 
can be enumerated as,
{“x”, “x”}, {"y", "y"}, {“xy”, “yx”}, 
{“xyy”, “yyx”}

Input  : str = "geeg"
Output : 4

La idea es crear un mapa. Utilizamos frecuencias de caracteres como claves y los recuentos correspondientes como valores. Podemos resolver este problema iterando sobre todas las substrings y contando las frecuencias de los caracteres en cada substring. Podemos actualizar las frecuencias de los caracteres mientras hacemos un bucle sobre las substrings, es decir, no habrá un bucle adicional para contar la frecuencia de los caracteres. En el siguiente código, se toma un mapa de clave ‘tipo de vector’ y valor ‘tipo int’ para almacenar la ocurrencia de ‘array de frecuencia de longitud 26’ de caracteres de substring. 

Una vez que se almacena la ocurrencia ‘o’ de cada array de frecuencia, los anagramas totales serán la suma de o*(o-1)/2 para todas las arrays de frecuencia diferentes porque si una substring en particular tiene anagramas ‘o’ en la string total o*(o Se pueden formar -1)/2 pares de anagramas. A continuación se muestra la implementación de la idea anterior. 

Implementación:

// C++ program to count total anagram
// substring of a string
#include <bits/stdc++.h>
using namespace std;
 
// Total number of lowercase characters
#define MAX_CHAR 26
 
// Utility method to return integer index
// of character 'c'
int toNum(char c)
{
    return (c - 'a');
}
 
// Returns count of total number of anagram
// substrings of string str
int countOfAnagramSubstring(string str)
{
    int N = str.length();
 
    // To store counts of substrings with given
    // set of frequencies.
    map<vector<int>, int> mp;
 
    // loop for starting index of substring
    for (int i=0; i<N; i++)
    {
        vector<int> freq(MAX_CHAR, 0);
 
        // loop for length of substring
        for (int j=i; j<N; j++)
        {
            // update freq array of current
            // substring
            freq[toNum(str[j])]++;
 
            // increase count corresponding
            // to this freq array
            mp[freq]++;
        }
    }
 
    // loop over all different freq array and
    // aggregate substring count
    int result = 0;
    for (auto it=mp.begin(); it!=mp.end(); it++)
    {
        int freq = it->second;
        result += ((freq) * (freq-1))/2;
    }
    return result;
}
 
//  Driver code to test above methods
int main()
{
    string str = "xyyx";
    cout << countOfAnagramSubstring(str) << endl;
    return 0;
}

import java.util.Arrays;
import java.util.HashMap;
 
public class anagramPairCount {
    public static void main(String[] args) {
        subString("kkkk");
    }
 
    static void subString(String s){
        HashMap<String, Integer> map= new HashMap<>();
 
        for(int i = 0; i < s.length(); i++){
            for(int j = i; j < s.length(); j++){
                char[] valC = s.substring(i, j+1).toCharArray();
                Arrays.sort(valC);
                String val = new String(valC);
                if (map.containsKey(val))
                    map.put(val, map.get(val)+1);
                else
                    map.put(val, 1);
            }
        }
        int anagramPairCount = 0;
        for(String key: map.keySet()){
            int n = map.get(key);
            anagramPairCount += (n * (n-1))/2;
        }
        System.out.println(anagramPairCount);
    }
}

# Python3 program to count total anagram
# substring of a string
def countOfAnagramSubstring(s):
     
    # Returns total number of anagram
    # substrings in s
    n = len(s)
    mp = dict()
     
    # loop for length of substring
    for i in range(n):
        sb = ''
        for j in range(i, n):
            sb = ''.join(sorted(sb + s[j]))
            mp[sb] = mp.get(sb, 0)
             
            # increase count corresponding
            # to this dict array
            mp[sb] += 1
 
    anas = 0
     
    # loop over all different dictionary
    # items and aggregate substring count
    for k, v in mp.items():
        anas += (v*(v-1))//2
    return anas
 
# Driver Code
s = "xyyx"
print(countOfAnagramSubstring(s))
 
# This code is contributed by fgaim

using System;
using System.Collections.Generic;
 
 
public class anagramPairCount {
    public static void Main() {
        subString("kkkk");
    }
 
    static void subString(String s){
        Dictionary<string, int> map= new Dictionary<string, int>();
 
        for(int i = 0; i < s.Length; i++){
            for(int j = i; j < s.Length; j++){
                char[] valC = s.Substring(i, j+1-i).ToCharArray();
                Array.Sort(valC);
                string val = new string(valC);
                if (map.ContainsKey(val))
                    map[val]=map[val]+1;
                else
                    map.Add(val, 1);
            }
        }
        int anagramPairCount = 0;
        foreach(string key in map.Keys){
            int n = map[key];
            anagramPairCount += (n * (n-1))/2;
        }
        Console.Write(anagramPairCount);
    }
}
 
// This code is contributed by AbhiThakur

<script>
 
// JavaScript code to implement the approach
 
function countOfAnagramSubstring(s){
     
    // Returns total number of anagram
    // substrings in s
    let n = s.length
    let mp = new Map()
     
    // loop for length of substring
    for(let i=0;i<n;i++){
        let sb = ''
        for(let j=i;j<n;j++){
            sb = (sb + s[j]).split('').sort().join('')
            if(mp.has(sb))
                mp.set(sb ,mp.get(sb)+1)
             
            // increase count corresponding
            // to this dict array
            else mp.set(sb, 1)
        }
    }
 
    let anas = 0
     
    // loop over all different dictionary
    // items and aggregate substring count
    for(let [k, v] of mp){
        anas += Math.floor((v*(v-1))/2)
    }
    return anas
}
 
// Driver Code
let s = "xyyx"
document.write(countOfAnagramSubstring(s),"</br>")
 
 
// This code is contributed by shinjanpatra
 
</script>

4

Complejidad temporal : O(N ² logN) 
Espacio auxiliar : O(N)

Este artículo es una contribución de Utkarsh Trivedi . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks. Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.