Dada una string str de longitud N y un entero K , la tarea es comprobar si una string tiene dos substrings de longitud K que no se superponen como anagramas.
Ejemplos:
Entrada: str = “ginfing”, K = 3
Salida: Sí
Explicación:
“gin” e “ing” son las dos substrings no superpuestas de longitud 3 que son anagramas.
Por lo tanto, la salida es Sí.Entrada: str = “ginig”, K = 3
Salida: No
Explicación:
En la string dada, no hay dos substrings no superpuestas de longitud 3 que sean anagramas. Tenga en cuenta que la substring «gin» y la substring «nig» son anagramas, pero se superponen, por lo que no se consideran.
Por lo tanto, la salida es No.
Enfoque: La idea para resolver este problema es atravesar la string dada y usar un conjunto para almacenar las substrings de longitud K y buscar dos substrings que no se superpongan presentes en la string dada. Siga los pasos a continuación:
- Inicialice un conjunto unordered_set para almacenar substrings de longitud K .
- Iterar sobre los caracteres de la string dada str usando una variable i .
- Si existe una string de longitud K que comienza en el índice (i – 1) en str, borre la string ordenada de longitud K del Conjunto .
- Si existe una string de longitud K que termina en el índice (i – 1) en str, inserte la string ordenada de longitud K en el Set .
- Si la substring ordenada de longitud K que comienza en el índice i se encuentra en el conjunto , entonces existen dos substrings de longitud K que no se superponen como anagramas en str . Por lo tanto, imprima «Sí» y salga del bucle . De lo contrario, inserte la substring ordenada de longitud K que comienza en el índice i en el Conjunto .
- Si no se encontraron pares de substrings después de recorrer toda la string, imprima «No».
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for the above approach
#include <bits/stdc++.h>
#include <iostream>
using namespace std;
// Function to check whether the string
// s has two non-overlapping substrings
// of length K as anagrams
void anagramPairs(string str, int K)
{
// Stores the substrings of length K
unordered_set<string> set;
int l = str.length();
// Iterate through every character
for (int i = 0; i < l; i++) {
// If there is a substring starting
// at index i - 1 of length K then
// erase that substring from set
if (i > 0 && K - (i - 1) - 1 < l) {
string s1 = str.substr(i - 1, K);
// Sort the substring
sort(s1.begin(), s1.end());
// Remove from set
set.erase(s1);
}
// If there is a substring of length
// K ending at index i - 1
if ((i - 1) - K + 1 >= 0) {
string s1 = str.substr(
(i - 1) - K + 1, K);
// Sort the substring
sort(s1.begin(), s1.end());
// Insert substring into the Set
set.insert(s1);
}
// If there is a substring of length
// K starting from the i-th index
if (K + i - 1 < l) {
// Check if the sorted
// substring is present in
// the set or not
string s1 = str.substr(i, K);
sort(s1.begin(), s1.end());
// If present in the Set
if (set.count(s1)) {
cout << "Yes";
return;
}
// Insert the sorted
// substring into the set
set.insert(s1);
}
}
// If not present in the Set
cout << "No";
}
// Driver Code
int main()
{
string str = "ginfing";
int K = 3;
// Function Call
anagramPairs(str, K);
return 0;
}
Java
// Java program for the above approach
import java.util.*;
class GFG
{
// Function to check whether the String
// s has two non-overlapping subStrings
// of length K as anagrams
static void anagramPairs(String str, int K)
{
// Stores the subStrings of length K
HashSet<String> set = new HashSet<String>();
int l = str.length();
// Iterate through every character
for (int i = 0; i < l; i++)
{
// If there is a subString starting
// at index i - 1 of length K then
// erase that subString from set
if (i > 0 && K - (i - 1) - 1 < l)
{
String s1 = str.substring(i - 1, K);
// Sort the subString
s1 = sortString(s1);
// Remove from set
set.remove(s1);
}
// If there is a subString of length
// K ending at index i - 1
if ((i - 1) - K + 1 >= 0)
{
String s1 = str.substring(
(i - 1) - K + 1, K);
// Sort the subString
s1 = sortString(s1);
// Insert subString into the Set
set.add(s1);
}
// If there is a subString of length
// K starting from the i-th index
if (K + i - 1 < l)
{
// Check if the sorted
// subString is present in
// the set or not
String s1 = str.substring(i, i+K);
s1 = sortString(s1);
// If present in the Set
if (set.contains(s1))
{
System.out.print("Yes");
return;
}
// Insert the sorted
// subString into the set
set.add(s1);
}
}
// If not present in the Set
System.out.print("No");
}
static String sortString(String inputString)
{
// convert input string to char array
char tempArray[] = inputString.toCharArray();
// sort tempArray
Arrays.sort(tempArray);
// return new sorted string
return new String(tempArray);
}
// Driver Code
public static void main(String[] args)
{
String str = "ginfing";
int K = 3;
// Function Call
anagramPairs(str, K);
}
}
// This code is contributed by Amit Katiyar
Python3
# Python3 program for the above approach
# Function to check whether the string
# s has two non-overlapping substrings
# of length K as anagrams
def anagramPairs(str, K):
# Stores the substrings of length K
sett = {}
l = len(str)
# Iterate through every character
for i in range(l):
# If there is a substring starting
# at index i - 1 of length K then
# erase that substring from sett
if (i > 0 and K - (i - 1) - 1 < l):
s1 = str[i - 1:i + K - 1]
# Sort the substring
s1 = sorted(s1)
# Remove from sett
del sett["".join(s1)]
# If there is a substring of length
# K ending at index i - 1
if ((i - 1) - K + 1 >= 0):
s1 = str[(i - 1) - K + 1:i]
# Sort the substring
s1 = sorted(s1)
# Insert substring into the Set
sett["".join(s1)] = 1
# If there is a substring of length
# K starting from the i-th index
if (K + i - 1 < l):
# Check if the sorted
# substring is present in
# the sett or not
s1 = str[i : i + K]
s1 = sorted(s1)
# If present in the Set
if "".join(s1) in sett:
print("Yes")
return
#Insert the sorted
# substring into the sett
sett["".join(s1)] = 1
# If not present in the Set
print("No")
# Driver Code
if __name__ == '__main__':
str = "ginfing"
K = 3
# Function Call
anagramPairs(str, K)
# This code is contributed by mohit kumar 29
C#
// C# program for the above approach
using System;
using System.Collections.Generic;
class GFG
{
// Function to check whether the String
// s has two non-overlapping subStrings
// of length K as anagrams
static void anagramPairs(String str, int K)
{
// Stores the subStrings of length K
HashSet<String> set = new HashSet<String>();
int l = str.Length;
// Iterate through every character
for (int i = 0; i < l; i++)
{
// If there is a subString starting
// at index i - 1 of length K then
// erase that subString from set
if (i > 0 && K - (i - 1) - 1 < l)
{
String s1 = str.Substring(i - 1, K);
// Sort the subString
s1 = sortString(s1);
// Remove from set
set.Remove(s1);
}
// If there is a subString of length
// K ending at index i - 1
if ((i - 1) - K + 1 >= 0)
{
String s1 = str.Substring(
(i - 1) - K + 1, K);
// Sort the subString
s1 = sortString(s1);
// Insert subString into the Set
set.Add(s1);
}
// If there is a subString of length
// K starting from the i-th index
if (K + i - 1 < l)
{
// Check if the sorted
// subString is present in
// the set or not
String s1 = str.Substring(i, K);
s1 = sortString(s1);
// If present in the Set
if (set.Contains(s1))
{
Console.Write("Yes");
return;
}
// Insert the sorted
// subString into the set
set.Add(s1);
}
}
// If not present in the Set
Console.Write("No");
}
static String sortString(String inputString)
{
// convert input string to char array
char []tempArray = inputString.ToCharArray();
// sort tempArray
Array.Sort(tempArray);
// return new sorted string
return new String(tempArray);
}
// Driver Code
public static void Main(String[] args)
{
String str = "ginfing";
int K = 3;
// Function Call
anagramPairs(str, K);
}
}
// This code is contributed by Princi Singh
Javascript
<script>
// JavaScript program for the above approach
// Function to check whether the string
// s has two non-overlapping substrings
// of length K as anagrams
function anagramPairs(str, K) {
// Stores the substrings of length K
let set = new Set();
let l = str.length;
// Iterate through every character
for (let i = 0; i < l; i++) {
// If there is a substring starting
// at index i - 1 of length K then
// erase that substring from set
if (i > 0 && K - (i - 1) - 1 < l) {
let s1 = str.substr(i - 1, K);
// Sort the substring
s1 = s1.split("").sort().join("")
// Remove from set
set.delete(s1);
}
// If there is a substring of length
// K ending at index i - 1
if ((i - 1) - K + 1 >= 0) {
let s1 = str.substr(
(i - 1) - K + 1, K);
// Sort the substring
s1 = s1.split("").sort().join("")
// Insert substring into the Set
set.add(s1);
}
// If there is a substring of length
// K starting from the i-th index
if (K + i - 1 < l) {
// Check if the sorted
// substring is present in
// the set or not
let s1 = str.substr(i, K);
s1 = s1.split("").sort().join("")
// If present in the Set
if (set.has(s1)) {
document.write("Yes");
return;
}
// Insert the sorted
// substring into the set
set.add(s1);
}
}
// If not present in the Set
document.write("No");
}
// Driver Code
let str = "ginfing";
let K = 3;
// Function Call
anagramPairs(str, K);
</script>
Producción:
Yes
Complejidad de tiempo: O(N*(K + K*log K))
Espacio auxiliar: O(N)
Publicación traducida automáticamente
Artículo escrito por ManikantaBandla y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA