Dada la string str de alfabetos en minúsculas y un número entero no negativo K . La tarea es encontrar el número de pares de caracteres en la string dada cuya diferencia de valor ASCII es exactamente K .
Ejemplos:
Entrada: str = “abcdab”, K = 0
Salida: 2
(a, a) y (b, b) son los únicos pares válidos.
Entrada: str = “geeksforgeeks”, K = 1
Salida: 8
(e, f), (e, f), (f, e), (f, e), (g, f),
(f, g), (s, r) y (r, s) son los pares válidos.
Enfoque: almacene la frecuencia de cada carácter en una array. Atraviese esta array de frecuencias para obtener la respuesta requerida. Existen dos casos:
- Si K = 0 , compruebe si el carácter similar aparece más de una vez, es decir, si freq[i] > 1 . En caso afirmativo, agregue (freq[i] * (freq[i] – 1)) / 2 a la cuenta.
- Si K != 0 , compruebe si existen dos caracteres con una diferencia de valor ASCII como K , digamos freq[i] y freq[j] . Luego agregue freq[i] * freq[j] al conteo.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
#define MAX 26
// Function to return the count of
// required pairs of characters
int countPairs(string str, int k)
{
// Length of the string
int n = str.size();
// To store the frequency
// of each character
int freq[MAX];
memset(freq, 0, sizeof freq);
// Update the frequency
// of each character
for (int i = 0; i < n; i++)
freq[str[i] - 'a']++;
// To store the required
// count of pairs
int cnt = 0;
// If ascii value difference is zero
if (k == 0) {
// If there exists similar characters
// more than once
for (int i = 0; i < MAX; i++)
if (freq[i] > 1)
cnt += ((freq[i] * (freq[i] - 1)) / 2);
}
else {
// If there exits characters with
// ASCII value difference as k
for (int i = 0; i < MAX; i++)
if (freq[i] > 0 && i + k < MAX && freq[i + k] > 0)
cnt += (freq[i] * freq[i + k]);
;
}
// Return the required count
return cnt;
}
// Driver code
int main()
{
string str = "abcdab";
int k = 0;
cout << countPairs(str, k);
return 0;
}
Java
// Java implementation of the approach
import java.util.Arrays;
class GFG
{
static int MAX = 26;
// Function to return the count of
// required pairs of characters
static int countPairs(char[] str, int k)
{
// Length of the string
int n = str.length;
// To store the frequency
// of each character
int[] freq = new int[MAX];
// Update the frequency
// of each character
for (int i = 0; i < n; i++)
{
freq[str[i] - 'a']++;
}
// To store the required
// count of pairs
int cnt = 0;
// If ascii value difference is zero
if (k == 0)
{
// If there exists similar characters
// more than once
for (int i = 0; i < MAX; i++)
{
if (freq[i] > 1)
{
cnt += ((freq[i] * (freq[i] - 1)) / 2);
}
}
}
else
{
// If there exits characters with
// ASCII value difference as k
for (int i = 0; i < MAX; i++)
{
if (freq[i] > 0 && i + k < MAX && freq[i + k] > 0)
{
cnt += (freq[i] * freq[i + k]);
}
}
;
}
// Return the required count
return cnt;
}
// Driver code
public static void main(String[] args)
{
String str = "abcdab";
int k = 0;
System.out.println(countPairs(str.toCharArray(), k));
}
}
/* This code contributed by PrinciRaj1992 */
Python3
# Python3 implementation of the approach
MAX = 26
# Function to return the count of
# required pairs of characters
def countPairs(string, k) :
# Length of the string
n = len(string);
# To store the frequency
# of each character
freq = [0] * MAX;
# Update the frequency
# of each character
for i in range(n) :
freq[ord(string[i]) -
ord('a')] += 1;
# To store the required
# count of pairs
cnt = 0;
# If ascii value difference is zero
if (k == 0) :
# If there exists similar characters
# more than once
for i in range(MAX) :
if (freq[i] > 1) :
cnt += ((freq[i] *
(freq[i] - 1)) // 2);
else :
# If there exits characters with
# ASCII value difference as k
for i in range(MAX) :
if (freq[i] > 0 and
i + k < MAX and
freq[i + k] > 0) :
cnt += (freq[i] * freq[i + k]);
# Return the required count
return cnt;
# Driver code
if __name__ == "__main__" :
string = "abcdab";
k = 0;
print(countPairs(string, k));
# This code is contributed by AnkitRai01
C#
// C# implementation of the approach
using System;
class GFG
{
static int MAX = 26;
// Function to return the count of
// required pairs of characters
static int countPairs(char[] str, int k)
{
// Length of the string
int n = str.Length;
// To store the frequency
// of each character
int[] freq = new int[MAX];
// Update the frequency
// of each character
for (int i = 0; i < n; i++)
{
freq[str[i] - 'a']++;
}
// To store the required
// count of pairs
int cnt = 0;
// If ascii value difference is zero
if (k == 0)
{
// If there exists similar characters
// more than once
for (int i = 0; i < MAX; i++)
{
if (freq[i] > 1)
{
cnt += ((freq[i] * (freq[i] - 1)) / 2);
}
}
}
else
{
// If there exits characters with
// ASCII value difference as k
for (int i = 0; i < MAX; i++)
{
if (freq[i] > 0 && i + k < MAX && freq[i + k] > 0)
{
cnt += (freq[i] * freq[i + k]);
}
}
;
}
// Return the required count
return cnt;
}
// Driver code
public static void Main(String[] args)
{
String str = "abcdab";
int k = 0;
Console.WriteLine(countPairs(str.ToCharArray(), k));
}
}
// This code has been contributed by 29AjayKumar
Javascript
<script>
// JavaScript implementation of the approach
const MAX = 26;
// Function to return the count of
// required pairs of characters
function countPairs(str, k) {
// Length of the string
var n = str.length;
// To store the frequency
// of each character
var freq = new Array(MAX).fill(0);
// Update the frequency
// of each character
for (var i = 0; i < n; i++) {
freq[str[i].charCodeAt(0) -
"a".charCodeAt(0)]++;
}
// To store the required
// count of pairs
var cnt = 0;
// If ascii value difference is zero
if (k === 0) {
// If there exists similar characters
// more than once
for (var i = 0; i < MAX; i++) {
if (freq[i] > 1) {
cnt += (freq[i] * (freq[i] - 1)) / 2;
}
}
} else {
// If there exits characters with
// ASCII value difference as k
for (var i = 0; i < MAX; i++) {
if (freq[i] > 0 && i + k < MAX &&
freq[i + k] > 0) {
cnt += freq[i] * freq[i + k];
}
}
}
// Return the required count
return cnt;
}
// Driver code
var str = "abcdab";
var k = 0;
document.write(countPairs(str.split(""), k));
</script>
Producción:
2
Complejidad de tiempo: O(|str| + MAX)
Espacio Auxiliar: O(MAX)
Publicación traducida automáticamente
Artículo escrito por pawan_asipu y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA