Recuento de strings distintas que se pueden obtener después de realizar exactamente un intercambio

Dada una string s que contiene caracteres del alfabeto inglés en minúsculas. La tarea es calcular el número de strings distintas que se pueden obtener después de realizar exactamente un intercambio.

Entrada: s = “geek”
Salida: 6
Explicación: Las siguientes son las strings formadas al hacer exactamente una
string de intercambio = [“egek”,”eegk”,”geek”,”geke”,”gkee”, “keeg”]
Por lo tanto , hay 6 strings distintas posibles.

Entrada: s= “ab”
Salida: 1

Enfoque: este problema se puede resolver utilizando HashMaps . Siga los pasos a continuación para resolver el problema dado.

• Verifique la cantidad de elementos únicos en la string s .
• Almacene las frecuencias de todos los caracteres únicos en un mapa.
• Declare una variable, digamos ans = 0 , para almacenar el número de strings distintas posibles.
• Iterar sobre la string e incrementar ans por el número de elementos aparte del elemento actual que se usará para construir una nueva string.
• Vuelva a iterar sobre la string y verifique si la frecuencia de algunos caracteres es mayor que 2. Si es así, incremente la respuesta en 1, ya que formarán solo una string única adicional.
• Devuelve ans como respuesta final.

A continuación se muestra la implementación del enfoque anterior.

// C++ program for above approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to count number of distinct
// string formed after one swap
long long countStrings(string S)
{
    long long N = S.size();
 
    // mp[] to store the frequency
    // of each character
    int mp[26] = { 0 };
 
    // For storing frequencies
    for (auto i : S) {
        mp[i - 'a']++;
    }
    long long ans = 0;
    for (auto i : S) {
        ans += N - mp[i - 'a'];
    }
    ans /= 2;
 
    for (int i = 0; i < 26; i++) {
        if (mp[i] >= 2) {
            ans++;
            break;
        }
    }
    return ans;
}
 
// Driver Code
int main()
{
    string S = "geek";
 
    // Function Call
    long long ans = countStrings(S);
    cout << ans << endl;
 
    return 0;
}

// Java code to implement the above approach
import java.util.*;
public class GFG
{
   
// Function to count number of distinct
// string formed after one swap
static long countStrings(String S)
{
    long N = S.length();
 
    // mp[] to store the frequency
    // of each character
    int mp[] = new int[26];
    for(int i = 0; i < 26; i++) {
        mp[i] = 0;
    }
 
    // For storing frequencies
    for (int i = 0; i < S.length(); i++) {
        mp[S.charAt(i) - 'a']++;
    }
    long ans = 0;
    for (int i = 0; i < S.length(); i++) {
        ans += N - mp[S.charAt(i) - 'a'];
    }
    ans /= 2;
 
    for (int i = 0; i < 26; i++) {
        if (mp[i] >= 2) {
            ans++;
            break;
        }
    }
    return ans;
}
 
// Driver code
public static void main(String args[])
{
    String S = "geek";
 
    // Function Call
    long ans = countStrings(S);
    System.out.println(ans);
}
}
 
// This code is contributed by Samim Hossain Mondal.

# Python code to implement the above approach
 
# Function to count number of distinct
# string formed after one swap
def countStrings(S):
    N = len(S);
 
    # mp to store the frequency
    # of each character
    mp = [0 for i in range(26)];
    for i in range(26):
        mp[i] = 0;
 
    # For storing frequencies
    for i in range(N):
        mp[ord(S[i]) - ord('a')] += 1;
 
    ans = 0;
    for i in range(N):
        ans += N - mp[ord(S[i]) - ord('a')];
 
    ans //= 2;
 
    for i in range(26):
        if (mp[i] >= 2):
            ans += 1;
            break;
 
    return ans;
 
# Driver code
if __name__ == '__main__':
    S = "geek";
 
    # Function Call
    ans = countStrings(S);
    print(ans);
 
# This code is contributed by 29AjayKumar

// C# code to implement the above approach
using System;
class GFG
{
   
// Function to count number of distinct
// string formed after one swap
static long countStrings(string S)
{
    long N = S.Length;
 
    // mp[] to store the frequency
    // of each character
    int []mp = new int[26];
    for(int i = 0; i < 26; i++) {
        mp[i] = 0;
    }
 
    // For storing frequencies
    for (int i = 0; i < S.Length; i++) {
        mp[S[i] - 'a']++;
    }
    long ans = 0;
    for (int i = 0; i < S.Length; i++) {
        ans += N - mp[S[i] - 'a'];
    }
    ans /= 2;
 
    for (int i = 0; i < 26; i++) {
        if (mp[i] >= 2) {
            ans++;
            break;
        }
    }
    return ans;
}
 
// Driver code
public static void Main()
{
    string S = "geek";
 
    // Function Call
    long ans = countStrings(S);
    Console.Write(ans);
}
}
 
// This code is contributed by Samim Hossain Mondal.

<script>
 
// JavaScript program for above approach
 
// Function to count number of distinct
// string formed after one swap
function countStrings(S)
{
    let N = S.length;
 
    // mp[] to store the frequency
    // of each character
    let mp = new Map();
 
    // For storing frequencies
    for(let i = 0; i < S.length; i++)
    {
        if (!mp.has(S[i].charCodeAt(0) - 'a'.charCodeAt(0)))
        {
            mp.set(S[i].charCodeAt(0) - 'a'.charCodeAt(0), 1);
        }
        else
        {
            mp.set(S[i].charCodeAt(0) -
                    'a'.charCodeAt(0),
                   mp.get(S[i].charCodeAt(0) -
                           'a'.charCodeAt(0)) + 1)
        }
    }
    let ans = 0;
    for(let i = 0; i < S.length; i++)
    {
        ans += N - mp.get(S[i].charCodeAt(0) -
                           'a'.charCodeAt(0));
    }
    ans = Math.floor(ans / 2)
 
    for(let i = 0; i < 26; i++)
    {
        if (mp.get(i) >= 2)
        {
            ans++;
            break;
        }
    }
    return ans;
}
 
// Driver Code
let S = "geek";
 
// Function Call
let ans = countStrings(S);
document.write(ans + '<br>')
 
// This code is contributed by Potta Lokesh
 
</script>

6

Complejidad de tiempo: O (N), ya que estamos usando un bucle para atravesar N veces, por lo que nos costará O (N) tiempo.
Espacio auxiliar: O(1), ya que no estamos utilizando ningún espacio adicional.