Dada una string S , la tarea es verificar si S contiene un par de substrings de longitud K que son anagramas entre sí y no contienen el carácter X en ellas. Si no existe tal substring, imprima -1 .
Ejemplos:
Entrada: S = “geeksforgeeks”, X = ‘f’, K = 5
Salida: geeks geeks
Explicación: Las
substrings “geeks” y “geeks” son anagramas entre sí y no contienen ‘f’.Entrada: S = “rotator”, X = ‘a’, K = 3
Salida: rot tor
Explicación: Las
substrings “rot” y “tor” son anagramas entre sí y no contienen ‘a’.
Enfoque:
La idea es generar una suma de prefijos sobre la base de los caracteres. Siga los pasos a continuación para resolver el problema:
- Iterar sobre la string y generar frecuencias de substrings mediante el uso de la array de suma de prefijos .
- Si una substring con la misma frecuencia de caracteres ya está presente en HashMap .
- De lo contrario, almacene la frecuencia de los caracteres de la substring con la substring actual en HashMap , si la frecuencia del carácter X en la substring es 0 .
A continuación se muestra la implementación del enfoque anterior:
Java
// Java Program to implement
// the above approach
import java.util.*;
// Class to represent a Substring
// in terms of frequency of
// characters present in it
class Substring {
int MOD = 1000000007;
// Store count of characters
int count[];
Substring() { count = new int[26]; }
public int hashCode()
{
int hash = 0;
for (int i = 0; i < 26; i++) {
hash += (i + 1) * count[i];
hash %= MOD;
}
return hash;
}
public boolean equals(Object o)
{
if (o == this)
return true;
if (!(o instanceof Substring))
return false;
Substring ob = (Substring)o;
for (int i = 0; i < 26; i++) {
if (ob.count[i] != count[i])
return false;
}
return true;
}
}
class GFG {
// Function to check anagrams
static void checkForAnagrams(String s, int n,
char X, int k)
{
boolean found = false;
// Prefix array to store frequencies
// of characters
int prefix[][] = new int[n + 1][26];
for (int i = 0; i < n; i++) {
prefix[i][s.charAt(i) - 97]++;
}
// Generate prefix sum
for (int i = 1; i < n; i++) {
for (int j = 0; j < 26; j++)
prefix[i][j] += prefix[i - 1][j];
}
// Map to store frequencies
HashMap<Substring, Integer> map
= new HashMap<>();
// Check for anagrams
for (int i = 0; i < n; i++) {
if (i + k > n)
break;
// Generate frequencies of characters
// of substring starting from i
Substring sub = new Substring();
for (int j = 0; j < 26; j++) {
sub.count[j]
= prefix[i + k - 1][j]
- (i - 1 >= 0
? prefix[i - 1][j]
: 0);
}
// Check if forbidden character is
// present, then continue
if (sub.count[X - 97] != 0)
continue;
// If already present in HashMap
if (map.containsKey(sub)) {
found = true;
// Print the substrings
System.out.println(
s.substring(map.get(sub),
map.get(sub) + k)
+ " " + s.substring(i, i + k));
break;
}
else {
map.put(sub, i);
}
}
// If no such substring is found
if (!found)
System.out.println("-1");
}
// Driver Code
public static void main(String[] args)
{
String s = "rotator";
int n = s.length();
char X = 'a';
int k = 3;
checkForAnagrams(s, n, X, k);
}
}
rot tor
Complejidad de Tiempo: O(N*26)
Espacio Auxiliar: O(N*26)
Publicación traducida automáticamente
Artículo escrito por jrishabh99 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA