Dadas dos strings S1 y S2 , la tarea es verificar si S2 contiene un anagrama de S1 como su substring .
Ejemplos:
Entrada: S1 = “ab”, S2 = “bbpobac”
Salida: Sí
Explicación: La string S2 contiene el anagrama “ba” de S1 (“ba”).Entrada: S1 = “ab”, S2 = “cbddaoo”
Salida: No
Enfoque: siga los pasos a continuación para resolver el problema:
- Inicialice dos Hashmaps s1hash y s2hash para almacenar la frecuencia de los alfabetos de las dos strings.
- Si la longitud de S1 es mayor que la longitud de S2 , imprima “NO” .
- Iterar sobre los caracteres de la string S1 y actualizar s1hash .
- Repita los caracteres de la string S2 utilizando la técnica de ventana deslizante y actualice HashMap en consecuencia.
- Para cualquier substring de S2 de longitud igual a la longitud de S1, si se encuentra que ambos Hashmaps son iguales, imprima «SÍ» .
- De lo contrario, escriba “NO” .
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ Program to implement
// the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to check if string s2
// contains anagram of the string
// s1 as its substring
bool checkAnagram(string s1, string s2)
{
// Stores frequencies of
// characters in substrings of s2
vector<int> s2hash(26, 0);
// Stores frequencies of
// characters in s1
vector<int> s1hash(26, 0);
int s1len = s1.size();
int s2len = s2.size();
// If length of s2 exceeds length of s1
if (s1len > s2len)
return false;
int left = 0, right = 0;
// Store frequencies of characters in first
// substring of length s1len in string s2
while (right < s1len) {
s1hash[s1[right] - 'a'] += 1;
s2hash[s2[right] - 'a'] += 1;
right++;
}
right -= 1;
// Perform Sliding Window technique
while (right < s2len) {
// If hashmaps are found to be
// identical for any substring
if (s1hash == s2hash)
return true;
right++;
if (right != s2len)
s2hash[s2[right] - 'a'] += 1;
s2hash[s2[left] - 'a'] -= 1;
left++;
}
return false;
}
// Driver Code
int main()
{
string s1 = "ab";
string s2 = "bbpobac";
if (checkAnagram(s1, s2))
cout << "YES\n";
else
cout << "No\n";
return 0;
}
Java
// Java program for the above approach
import java.io.*;
import java.util.*;
class GFG
{
// Function to check if string s2
// contains anagram of the string
// s1 as its substring
public static boolean checkAnagram(String s1, String s2)
{
// Stores frequencies of
// characters in substrings of s2
int s2hash[] = new int[26];
// Stores frequencies of
// characters in s1
int s1hash[] = new int[26];
int s1len = s1.length();
int s2len = s2.length();
// If length of s2 exceeds length of s1
if (s1len > s2len)
return false;
int left = 0, right = 0;
// Store frequencies of characters in first
// substring of length s1len in string s2
while (right < s1len)
{
s1hash[s1.charAt(right) - 'a'] += 1;
s2hash[s2.charAt(right) - 'a'] += 1;
right++;
}
right -= 1;
// Perform Sliding Window technique
while (right < s2len) {
// If hashmaps are found to be
// identical for any substring
if (Arrays.equals(s1hash, s2hash))
return true;
right++;
if (right != s2len)
s2hash[s2.charAt(right) - 'a'] += 1;
s2hash[s2.charAt(left) - 'a'] -= 1;
left++;
}
return false;
}
// Driver Code
public static void main(String[] args)
{
String s1 = "ab";
String s2 = "bbpobac";
if (checkAnagram(s1, s2))
System.out.println("YES");
else
System.out.println("No");
}
}
// This code is contributed by kingash.
Python3
# Python 3 Program to implement
# the above approach
# Function to check if string s2
# contains anagram of the string
# s1 as its substring
def checkAnagram(s1, s2):
# Stores frequencies of
# characters in substrings of s2
s2hash = [0 for i in range(26)]
# Stores frequencies of
# characters in s1
s1hash = [0 for i in range(26)]
s1len = len(s1)
s2len = len(s2)
# If length of s2 exceeds length of s1
if (s1len > s2len):
return False
left = 0
right = 0
# Store frequencies of characters in first
# substring of length s1len in string s2
while (right < s1len):
s1hash[ord(s1[right]) - 97] += 1
s2hash[ord(s2[right]) - 97] += 1
right += 1
right -= 1
# Perform Sliding Window technique
while (right < s2len):
# If hashmaps are found to be
# identical for any substring
if (s1hash == s2hash):
return True
right += 1
if (right != s2len):
s2hash[ord(s2[right]) - 97] += 1
s2hash[ord(s2[left]) - 97] -= 1
left += 1
return False
# Driver Code
if __name__ == '__main__':
s1 = "ab"
s2 = "bbpobac"
if (checkAnagram(s1, s2)):
print("YES")
else:
print("No")
# This code is contributed by ipg2016107
C#
// C# Program to implement
// the above approach
using System;
using System.Collections.Generic;
class GFG{
// Function to check if string s2
// contains anagram of the string
// s1 as its substring
static bool checkAnagram(string s1, string s2)
{
// Stores frequencies of
// characters in substrings of s2
List<int> s2hash = new List<int>();
for(int i=0;i<26;i++)
s2hash.Add(0);
// Stores frequencies of
// characters in s1
List<int> s1hash = new List<int>();
for(int i=0;i<26;i++)
s1hash.Add(0);
int s1len = s1.Length;
int s2len = s2.Length;
// If length of s2 exceeds length of s1
if (s1len > s2len)
return false;
int left = 0, right = 0;
// Store frequencies of characters in first
// substring of length s1len in string s2
while (right < s1len) {
s1hash[s1[right] - 'a'] += 1;
s2hash[s2[right] - 'a'] += 1;
right++;
}
right -= 1;
// Perform Sliding Window technique
while (right < s2len) {
// If hashmaps are found to be
// identical for any substring
if (s1hash == s2hash)
return true;
right++;
if(right != s2len)
s2hash[s2[right] - 'a'] += 1;
s2hash[s2[left] - 'a'] -= 1;
left++;
}
return false;
}
// Driver Code
public static void Main()
{
string s1 = "ab";
string s2 = "bbpobac";
if (checkAnagram(s1, s2)==true)
Console.WriteLine("NO");
else
Console.WriteLine("YES");
}
}
// This code is contributed by bgangawar59.
Javascript
<script>
// Javascript Program to implement
// the above approach
// Function to check if string s2
// contains anagram of the string
// s1 as its substring
function checkAnagram(s1, s2)
{
// Stores frequencies of
// characters in substrings of s2
var s2hash = Array(26).fill(0);
// Stores frequencies of
// characters in s1
var s1hash = Array(26).fill(0);
var s1len = s1.length;
var s2len = s2.length;
// If length of s2 exceeds length of s1
if (s1len > s2len)
return false;
var left = 0, right = 0;
// Store frequencies of characters in first
// substring of length s1len in string s2
while (right < s1len) {
s1hash[s1[right].charCodeAt(0) - 'a'.charCodeAt(0)] += 1;
s2hash[s2[right].charCodeAt(0) - 'a'.charCodeAt(0)] += 1;
right++;
}
right -= 1;
// Perform Sliding Window technique
while (right < s2len) {
var ans = true;
// If hashmaps are found to be
// identical for any substring
for(var i =0; i<26; i++)
{
if(s1hash[i]!=s2hash[i])
{
ans = false;
}
}
if(ans)
return true;
right++;
if (right != s2len)
s2hash[s2[right].charCodeAt(0) - 'a'.charCodeAt(0)] += 1;
s2hash[s2[left].charCodeAt(0) - 'a'.charCodeAt(0)] -= 1;
left++;
}
return false;
}
// Driver Code
var s1 = "ab";
var s2 = "bbpobac";
if (checkAnagram(s1, s2))
document.write( "YES");
else
document.write( "No");
// This code is contributed by importantly.
</script>
Producción:
YES
Complejidad de Tiempo: O(26 * len(S2))
Espacio Auxiliar: O(26)