Dadas dos strings de alfabetos en minúsculas y un valor k, la tarea es encontrar si dos strings son K-anagramas entre sí o no.
Dos strings se denominan k-anagramas si las siguientes dos condiciones son verdaderas.
- Ambos tienen el mismo número de caracteres.
- Dos strings pueden convertirse en anagramas cambiando como máximo k caracteres en una string.
Ejemplos:
Input: str1 = "anagram" , str2 = "grammar" , k = 3 Output: Yes Explanation: We can update maximum 3 values and it can be done in changing only 'r' to 'n' and 'm' to 'a' in str2. Input: str1 = "geeks", str2 = "eggkf", k = 1 Output: No Explanation: We can update or modify only 1 value but there is a need of modifying 2 characters. i.e. g and f in str 2.
Método 1:
A continuación se muestra una solución para verificar si dos strings son k-anagramas entre sí o no.
- Almacena la ocurrencia de todos los caracteres de ambas strings en arrays de conteo separadas.
- Cuente el número de caracteres diferentes en ambas strings (en esto, si una string tiene 4 a y la segunda tiene 3 ‘a’, también se contará.
- Si el recuento de caracteres diferentes es menor o igual que k, devuelve verdadero o falso.
Implementación:
C++
// C++ program to check if two strings are k anagram
// or not.
#include<bits/stdc++.h>
using namespace std;
const int MAX_CHAR = 26;
// Function to check that string is k-anagram or not
bool arekAnagrams(string str1, string str2, int k)
{
// If both strings are not of equal
// length then return false
int n = str1.length();
if (str2.length() != n)
return false;
int count1[MAX_CHAR] = {0};
int count2[MAX_CHAR] = {0};
// Store the occurrence of all characters
// in a hash_array
for (int i = 0; i < n; i++)
count1[str1[i]-'a']++;
for (int i = 0; i < n; i++)
count2[str2[i]-'a']++;
int count = 0;
// Count number of characters that are
// different in both strings
for (int i = 0; i < MAX_CHAR; i++)
if (count1[i] > count2[i])
count = count + abs(count1[i]-count2[i]);
// Return true if count is less than or
// equal to k
return (count <= k);
}
// Driver code
int main()
{
string str1 = "anagram";
string str2 = "grammar";
int k = 2;
if (arekAnagrams(str1, str2, k))
cout << "Yes";
else
cout<< "No";
return 0;
}
Java
// Java program to check if two strings are k anagram
// or not.
public class GFG {
static final int MAX_CHAR = 26;
// Function to check that string is k-anagram or not
static boolean arekAnagrams(String str1, String str2,
int k)
{
// If both strings are not of equal
// length then return false
int n = str1.length();
if (str2.length() != n)
return false;
int[] count1 = new int[MAX_CHAR];
int[] count2 = new int[MAX_CHAR];
int count = 0;
// Store the occurrence of all characters
// in a hash_array
for (int i = 0; i < n; i++)
count1[str1.charAt(i) - 'a']++;
for (int i = 0; i < n; i++)
count2[str2.charAt(i) - 'a']++;
// Count number of characters that are
// different in both strings
for (int i = 0; i < MAX_CHAR; i++)
if (count1[i] > count2[i])
count = count + Math.abs(count1[i] -
count2[i]);
// Return true if count is less than or
// equal to k
return (count <= k);
}
// Driver code
public static void main(String args[])
{
String str1 = "anagram";
String str2 = "grammar";
int k = 2;
if (arekAnagrams(str1, str2, k))
System.out.println("Yes");
else
System.out.println("No");
}
}
// This code is contributed by Sumit Ghosh
Python3
# Python3 program to check if two
# strings are k anagram or not.
MAX_CHAR = 26
# Function to check that is
# k-anagram or not
def arekAnagrams(str1, str2, k) :
# If both strings are not of equal
# length then return false
n = len(str1)
if (len(str2)!= n) :
return False
count1 = [0] * MAX_CHAR
count2 = [0] * MAX_CHAR
# Store the occurrence of all
# characters in a hash_array
for i in range(n):
count1[ord(str1[i]) -
ord('a')] += 1
for i in range(n):
count2[ord(str2[i]) -
ord('a')] += 1
count = 0
# Count number of characters that
# are different in both strings
for i in range(MAX_CHAR):
if (count1[i] > count2[i]) :
count = count + abs(count1[i] -
count2[i])
# Return true if count is less
# than or equal to k
return (count <= k)
# Driver Code
if __name__ == '__main__':
str1 = "anagram"
str2 = "grammar"
k = 2
if (arekAnagrams(str1, str2, k)):
print("Yes")
else:
print("No")
# This code is contributed
# by SHUBHAMSINGH10
C#
// C# program to check if two
// strings are k anagram or not.
using System;
class GFG {
static int MAX_CHAR = 26;
// Function to check that
// string is k-anagram or not
static bool arekAnagrams(string str1,
string str2,
int k)
{
// If both strings are not of equal
// length then return false
int n = str1.Length;
if (str2.Length != n)
return false;
int[] count1 = new int[MAX_CHAR];
int[] count2 = new int[MAX_CHAR];
int count = 0;
// Store the occurrence
// of all characters
// in a hash_array
for (int i = 0; i < n; i++)
count1[str1[i] - 'a']++;
for (int i = 0; i < n; i++)
count2[str2[i] - 'a']++;
// Count number of characters that are
// different in both strings
for (int i = 0; i < MAX_CHAR; i++)
if (count1[i] > count2[i])
count = count + Math.Abs(count1[i] -
count2[i]);
// Return true if count is
// less than or equal to k
return (count <= k);
}
// Driver code
public static void Main()
{
string str1 = "anagram";
string str2 = "grammar";
int k = 2;
if (arekAnagrams(str1, str2, k))
Console.Write("Yes");
else
Console.Write("No");
}
}
// This code is contributed by nitin mittal.
PHP
<?php
// PHP program to check
// if two strings are
// k anagram or not.
$MAX_CHAR = 26;
// Function to check that
// string is k-anagram or not
function arekAnagrams($str1, $str2, $k)
{
global $MAX_CHAR;
// If both strings are not of
// equal length then return false
$n = strlen($str1);
if (strlen($str2) != $n)
return false;
$count1 = (0);
$count2 = (0);
// Store the occurrence of all
// characters in a hash_array
$count = 0;
// Count number of characters that
// are different in both strings
for ($i = 0; $i < $MAX_CHAR; $i++)
if ($count1[$i] > $count2[$i])
$count = $count + abs($count1[$i] -
$count2[$i]);
// Return true if count is
// less than or equal to k
return ($count <= $k);
}
// Driver Code
$str1 = "anagram";
$str2 = "grammar";
$k = 2;
if (arekAnagrams($str1, $str2, $k))
echo "Yes";
else
echo "No";
// This code is contributed by m_kit
?>
Javascript
<script>
// Javascript program to check if two
// strings are k anagram or not.
let MAX_CHAR = 26;
// Function to check that string is
// k-anagram or not
function arekAnagrams(str1, str2, k)
{
// If both strings are not of equal
// length then return false
let n = str1.length;
if (str2.length != n)
return false;
let count1 = new Array(MAX_CHAR);
let count2 = new Array(MAX_CHAR);
let count = 0;
// Store the occurrence of all characters
// in a hash_array
for(let i = 0; i < n; i++)
count1[str1[i].charCodeAt(0) -
'a'.charCodeAt(0)]++;
for(let i = 0; i < n; i++)
count2[str2[i].charCodeAt(0) -
'a'.charCodeAt(0)]++;
// Count number of characters that are
// different in both strings
for(let i = 0; i < MAX_CHAR; i++)
if (count1[i] > count2[i])
count = count + Math.abs(count1[i] -
count2[i]);
// Return true if count is less than or
// equal to k
return (count <= k);
}
// Driver code
let str1 = "anagram";
let str2 = "grammar";
let k = 2;
if (arekAnagrams(str1, str2, k))
document.write("Yes");
else
document.write("No");
// This code is contributed by rag2127
</script>
Producción
Yes
Complejidad temporal: O(n)
Espacio auxiliar: O(1)
Método 2: podemos optimizar la solución anterior. Aquí usamos solo una array de conteo para almacenar conteos de caracteres en str1. Atravesamos str2 y disminuimos la aparición de cada carácter en la array de conteo que está presente en str2. Si encontramos un carácter que no está en str1, incrementamos el conteo de diferentes caracteres. Si el recuento de caracteres diferentes se vuelve más que k, devolvemos falso.
Implementación:
C++
// Optimized C++ program to check if two strings
// are k anagram or not.
#include<bits/stdc++.h>
using namespace std;
const int MAX_CHAR = 26;
// Function to check if str1 and str2 are k-anagram
// or not
bool areKAnagrams(string str1, string str2, int k)
{
// If both strings are not of equal
// length then return false
int n = str1.length();
if (str2.length() != n)
return false;
int hash_str1[MAX_CHAR] = {0};
// Store the occurrence of all characters
// in a hash_array
for (int i = 0; i < n ; i++)
hash_str1[str1[i]-'a']++;
// Store the occurrence of all characters
// in a hash_array
int count = 0;
for (int i = 0; i < n ; i++)
{
if (hash_str1[str2[i]-'a'] > 0)
hash_str1[str2[i]-'a']--;
else
count++;
if (count > k)
return false;
}
// Return true if count is less than or
// equal to k
return true;
}
// Driver code
int main()
{
string str1 = "fodr";
string str2 = "gork";
int k = 2;
if (areKAnagrams(str1, str2, k) == true)
cout << "Yes";
else
cout << "No";
return 0;
}
Java
// Optimized Java program to check if two strings
// are k anagram or not.
public class GFG {
static final int MAX_CHAR = 26;
// Function to check if str1 and str2 are k-anagram
// or not
static boolean areKAnagrams(String str1, String str2,
int k)
{
// If both strings are not of equal
// length then return false
int n = str1.length();
if (str2.length() != n)
return false;
int[] hash_str1 = new int[MAX_CHAR];
// Store the occurrence of all characters
// in a hash_array
for (int i = 0; i < n ; i++)
hash_str1[str1.charAt(i)-'a']++;
// Store the occurrence of all characters
// in a hash_array
int count = 0;
for (int i = 0; i < n ; i++)
{
if (hash_str1[str2.charAt(i)-'a'] > 0)
hash_str1[str2.charAt(i)-'a']--;
else
count++;
if (count > k)
return false;
}
// Return true if count is less than or
// equal to k
return true;
}
// Driver code
public static void main(String args[])
{
String str1 = "fodr";
String str2 = "gork";
int k = 2;
if (areKAnagrams(str1, str2, k) == true)
System.out.println("Yes");
else
System.out.println("No");
}
}
// This code is contributed by Sumit Ghosh
Python3
# Optimized Python3 program
# to check if two strings
# are k anagram or not.
MAX_CHAR = 26;
# Function to check if str1
# and str2 are k-anagram or not
def areKAnagrams(str1, str2, k):
# If both strings are
# not of equal length
# then return false
n = len(str1);
if (len(str2) != n):
return False;
hash_str1 = [0]*(MAX_CHAR);
# Store the occurrence of
# all characters in a hash_array
for i in range(n):
hash_str1[ord(str1[i]) - ord('a')]+=1;
# Store the occurrence of all
# characters in a hash_array
count = 0;
for i in range(n):
if (hash_str1[ord(str2[i]) - ord('a')] > 0):
hash_str1[ord(str2[i]) - ord('a')]-=1;
else:
count+=1;
if (count > k):
return False;
# Return true if count is
# less than or equal to k
return True;
# Driver code
str1 = "fodr";
str2 = "gork";
k = 2;
if (areKAnagrams(str1, str2, k) == True):
print("Yes");
else:
print("No");
# This code is contributed by mits
C#
// Optimized C# program to check if two strings
// are k anagram or not.
using System;
class GFG {
static int MAX_CHAR = 26;
// Function to check if str1 and str2 are k-anagram
// or not
static bool areKAnagrams(String str1, String str2,
int k)
{
// If both strings are not of equal
// [i] then return false
int n = str1.Length;
if (str2.Length != n)
return false;
int[] hash_str1 = new int[MAX_CHAR];
// Store the occurrence of all characters
// in a hash_array
for (int i = 0; i < n ; i++)
hash_str1[str1[i]-'a']++;
// Store the occurrence of all characters
// in a hash_array
int count = 0;
for (int i = 0; i < n ; i++)
{
if (hash_str1[str2[i]-'a'] > 0)
hash_str1[str2[i]-'a']--;
else
count++;
if (count > k)
return false;
}
// Return true if count is less than or
// equal to k
return true;
}
// Driver code
static void Main()
{
String str1 = "fodr";
String str2 = "gork";
int k = 2;
if (areKAnagrams(str1, str2, k) == true)
Console.Write("Yes");
else
Console.Write("No");
}
}
// This code is contributed by Anuj_67
PHP
<?php
// Optimized PHP program
// to check if two strings
// are k anagram or not.
$MAX_CHAR = 26;
// Function to check if str1
// and str2 are k-anagram or not
function areKAnagrams($str1,
$str2, $k)
{
global $MAX_CHAR;
// If both strings are
// not of equal length
// then return false
$n = strlen($str1);
if (strlen($str2) != $n)
return false;
$hash_str1 = array(0);
// Store the occurrence of
// all characters in a hash_array
for ($i = 0; $i < $n ; $i++)
$hash_str1[$str1[$i] - 'a']++;
// Store the occurrence of all
// characters in a hash_array
$count = 0;
for ($i = 0; $i < $n ; $i++)
{
if ($hash_str1[$str2[$i] - 'a'] > 0)
$hash_str1[$str2[$i] - 'a']--;
else
$count++;
if ($count > $k)
return false;
}
// Return true if count is
// less than or equal to k
return true;
}
// Driver code
$str1 = "fodr";
$str2 = "gork";
$k = 2;
if (areKAnagrams($str1, $str2, $k) == true)
echo "Yes";
else
echo "No";
// This code is contributed by ajit
?>
Javascript
<script>
// Optimized Javascript program
// to check if two strings
// are k anagram or not.
let MAX_CHAR = 26;
// Function to check if str1 and
// str2 are k-anagram
// or not
function areKAnagrams(str1, str2, k)
{
// If both strings are not of equal
// [i] then return false
let n = str1.length;
if (str2.length != n)
return false;
let hash_str1 = Array(MAX_CHAR);
hash_str1.fill(0);
// Store the occurrence of all characters
// in a hash_array
for (let i = 0; i < n ; i++)
hash_str1[str1[i].charCodeAt()-
'a'.charCodeAt()]++;
// Store the occurrence of all characters
// in a hash_array
let count = 0;
for (let i = 0; i < n ; i++)
{
if (hash_str1[str2[i].charCodeAt()-
'a'.charCodeAt()] > 0)
hash_str1[str2[i].charCodeAt()-
'a'.charCodeAt()]--;
else
count++;
if (count > k)
return false;
}
// Return true if count is less than or
// equal to k
return true;
}
let str1 = "fodr";
let str2 = "gork";
let k = 2;
if (areKAnagrams(str1, str2, k) == true)
document.write("Yes");
else
document.write("No");
</script>
Producción
Yes
Complejidad temporal: O(n)
Espacio auxiliar: O(1)
Método 3:
- En este método, la idea es inicializar una array o una lista y el caso base sería verificar las strings y si tienen diferentes longitudes, entonces no pueden formar un anagrama.
- De lo contrario, convierta las strings en una array de caracteres y ordénelas.
- Luego itere hasta la longitud de la string y si el carácter no es igual, agréguelo a la lista y verifique si el tamaño de la lista es menor que K, entonces es posible formar el anagrama K de lo contrario.
A continuación se muestra la implementación del enfoque anterior:
C++
// CPP program for the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to check k
// anagram of two strings
bool kAnagrams(string str1, string str2, int k)
{
int flag = 0;
// First Condition: If both the
// strings have different length ,
// then they cannot form anagram
if (str1.length() != str2.length())
return false;
int n = str1.length();
// Converting str1 to Character Array arr1
char arr1[n];
// Converting str2 to Character Array arr2
char arr2[n];
strcpy(arr1, str1.c_str());
strcpy(arr2, str2.c_str());
// Sort arr1 in increasing order
sort(arr1, arr1 + n);
// Sort arr2 in increasing order
sort(arr2, arr2 + n);
vector<char> list;
// Iterate till str1.length()
for (int i = 0; i < str1.length(); i++) {
// Condition if arr1[i] is
// not equal to arr2[i]
// then add it to list
if (arr1[i] != arr2[i]) {
list.push_back(arr2[i]);
}
}
// Condition to check if
// strings for K-anagram or not
if (list.size() <= k)
flag = 1;
if (flag == 1)
return true;
else
return false;
}
// Driver Code
int main()
{
string str1 = "anagram", str2 = "grammar";
int k = 3;
// Function Call
kAnagrams(str1, str2, k);
if (kAnagrams(str1, str2, k) == true)
cout << "Yes";
else
cout << "No";
// This code is contributed by bolliranadheer
}
Java
// Java program for the above approach
import java.util.*;
class GFG{
// Function to check k
// anagram of two strings
public static boolean kAnagrams(String str1,
String str2, int k)
{
int flag = 0;
List<Character> list = new ArrayList<>();
// First Condition: If both the
// strings have different length ,
// then they cannot form anagram
if (str1.length() != str2.length())
System.exit(0);
// Converting str1 to Character Array arr1
char arr1[] = str1.toCharArray();
// Converting str2 to Character Array arr2
char arr2[] = str2.toCharArray();
// Sort arr1 in increasing order
Arrays.sort(arr1);
// Sort arr2 in increasing order
Arrays.sort(arr2);
// Iterate till str1.length()
for (int i = 0; i < str1.length(); i++)
{
// Condition if arr1[i] is
// not equal to arr2[i]
// then add it to list
if (arr1[i] != arr2[i])
{
list.add(arr2[i]);
}
}
// Condition to check if
// strings for K-anagram or not
if (list.size() <= k)
flag = 1;
if (flag == 1)
return true;
else
return false;
}
// Driver Code
public static void main(String[] args)
{
String str1 = "fodr";
String str2 = "gork";
int k = 2;
// Function Call
kAnagrams(str1, str2, k);
if (kAnagrams(str1, str2, k) == true)
System.out.println("Yes");
else
System.out.println("No");
}
}
Python3
# Python 3 program for the above approach
import sys
# Function to check k
# anagram of two strings
def kAnagrams(str1, str2, k):
flag = 0
list1 = []
# First Condition: If both the
# strings have different length ,
# then they cannot form anagram
if (len(str1) != len(str2)):
sys.exit()
# Converting str1 to Character Array arr1
arr1 = list(str1)
# Converting str2 to Character Array arr2
arr2 = list(str2)
# Sort arr1 in increasing order
arr1.sort()
# Sort arr2 in increasing order
arr2.sort()
# Iterate till str1.length()
for i in range(len(str1)):
# Condition if arr1[i] is
# not equal to arr2[i]
# then add it to list
if (arr1[i] != arr2[i]):
list1.append(arr2[i])
# Condition to check if
# strings for K-anagram or not
if (len(list1) <= k):
flag = 1
if (flag == 1):
return True
else:
return False
# Driver Code
if __name__ == "__main__":
str1 = "fodr"
str2 = "gork"
k = 2
# Function Call
kAnagrams(str1, str2, k)
if (kAnagrams(str1, str2, k) == True):
print("Yes")
else:
print("No")
C#
// C# program for the above approach
using System;
using System.Collections.Generic;
public class GFG
{
// Function to check k
// anagram of two strings
public static bool kAnagrams(string str1, string str2, int k)
{
int flag = 0;
List<char> list = new List<char>();
// First Condition: If both the
// strings have different length ,
// then they cannot form anagram
if (str1.Length != str2.Length)
{
return false;
}
// Converting str1 to Character Array arr1
char[] arr1 = str1.ToCharArray();
// Converting str2 to Character Array arr2
char[] arr2 = str2.ToCharArray();
// Sort arr1 in increasing order
Array.Sort(arr1);
// Sort arr2 in increasing order
Array.Sort(arr2);
// Iterate till str1.length()
for (int i = 0; i < str1.Length; i++)
{
// Condition if arr1[i] is
// not equal to arr2[i]
// then add it to list
if (arr1[i] != arr2[i])
{
list.Add(arr2[i]);
}
}
// Condition to check if
// strings for K-anagram or not
if (list.Count <= k)
flag = 1;
if (flag == 1)
return true;
else
return false;
}
// Driver Code
static public void Main ()
{
string str1 = "fodr";
string str2 = "gork";
int k = 2;
// Function Call
kAnagrams(str1, str2, k);
if (kAnagrams(str1, str2, k) == true)
Console.WriteLine("Yes");
else
Console.WriteLine("No");
}
}
// This code is contributed by avanitrachhadiya2155
Javascript
<script>
// Javascript program for the above approach
// Function to check k
// anagram of two strings
function kAnagrams(str1, str2, k)
{
let flag = 0;
let list = [];
// First Condition: If both the
// strings have different length ,
// then they cannot form anagram
if (str1.length != str2.length)
{
return false;
}
// Converting str1 to Character Array arr1
let arr1 = str1.split('');
// Converting str2 to Character Array arr2
let arr2 = str2.split('');
// Sort arr1 in increasing order
arr1.sort();
// Sort arr2 in increasing order
arr2.sort();
// Iterate till str1.length()
for(let i = 0; i < str1.length; i++)
{
// Condition if arr1[i] is
// not equal to arr2[i]
// then add it to list
if (arr1[i] != arr2[i])
{
list.push(arr2[i]);
}
}
// Condition to check if
// strings for K-anagram or not
if (list.length <= k)
flag = 1;
if (flag == 1)
return true;
else
return false;
}
// Driver code
let str1 = "fodr";
let str2 = "gork";
let k = 2;
// Function Call
kAnagrams(str1, str2, k);
if (kAnagrams(str1, str2, k) == true)
document.write("Yes");
else
document.write("No");
// This code is contributed by suresh07
</script>
Producción
Yes
Complejidad temporal : O(n)
Espacio auxiliar : O(1)
Este artículo es una contribución de Sahil Chhabra (akku) . 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.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA