Encuentra todas las substrings que son anagramas de otra substring de la string S

Dada una string S , la tarea es encontrar todas las substrings en la string S , que es un anagrama de otra substring diferente en la string S. Las diferentes substrings significan que la substring comienza en el índice diferente.

Ejemplos:

Entrada: S = “aba”
Salida: aa ab ba
Explicación: Las
siguientes substrings son anagramas de otra substring de la string S:

1. “a”: La substring “a” es el anagrama de la substring “a”(= {S[0]}).
2. “a”: La substring “a” es el anagrama de la substring “a”(= {S[2]}).
3. “ab”: La substring “ab” es el anagrama de la substring “ba”(= {S[1], S[2]}).
4. “ba”: La substring “ba” es el anagrama de la substring “ab”(= {S[0], S[2]}).

Entrada: S = “abcd”
Salida: []

Enfoque: el problema dado se puede resolver utilizando Hashing almacenando los anagramas de cada substring de la string S e imprimiendo la substring resultante. Siga los pasos a continuación para resolver el problema dado:

• Inicialice un HashMap que almacene todos los anagramas de cada substring de la string S .
• Genere todas las substrings posibles de S y para cada substring, digamos str almacene la substring en el HashMap mapeado con la clave como la string ordenada str .
• Recorra el HashMap e imprima todas las strings asociadas con cada clave cuyo número de strings asociadas con cada string sea al menos 1 .

A continuación se muestra la implementación del enfoque anterior:

# Python program for the above approach
 
import collections
 
# Function to find all the substrings
# whose anagram exist as a different
# substring in S
def findAnagrams(S):
   
    # Stores the lists of anagrams of
    # each substring of S
    Map = collections.defaultdict(list)
     
    # Stores the length of S
    N = len(S)
     
    # Generate all substrings of S
    for i in range(N):
        for j in range(i, N):
             
            # Store the current substring
            # of the string S
            curr = S[i: j + 1]
             
            # Key is the sorted substring
            key = "".join(sorted(curr))
             
            # Add the sorted substring
            # to the dictionary
            Map[key].append(curr)
     
    # Store the final result
    result = []
     
    # Iterate over values of dictionary
    for vals in Map.values():
         
        # If length of list > 1
        if len(vals) > 1:
            
            # Print all the strings
            for v in vals:
                  print(v, end =" ")   
 
# Driver Code
 
S = "aba"
findAnagrams(S)

ab ba a a

Complejidad de Tiempo: O(N ³ )
Espacio Auxiliar: O(N ² )