Dada una string, encuentre el número de permutaciones únicas que se pueden obtener intercambiando dos índices de modo que los elementos en estos índices sean distintos.
NOTA: El intercambio siempre se realiza en la string original.
Ejemplos:
Entrada: str = “sstt”
Salida: 5
Explicación:
Intercambiar str[0] con str[2], la string obtuvo “tsst” que es válida (str[0]!=str[2])
Intercambiar str[0] con str [3]. string obtenida «tsts»
Intercambiar str[1] con str[2], string obtenida «stst»
Intercambiar str[1] con str[3], string obtenida «stts»
Por lo tanto, se pueden obtener un total de 5 strings, incluida la string dada (» sstt”)Entrada: str = «abcd»
Salida: 7
Enfoque: el problema se puede resolver utilizando HashMap mediante los siguientes pasos:
- Cree un mapa hash y almacene la frecuencia de cada carácter de la string dada.
- Cree una variable count, para almacenar el número total de caracteres en la string dada, es decir, count=str.length() y una variable ans para almacenar el número de permutaciones únicas posibles e inicializar ans=0.
- Atraviesa la string y para cada carácter:
- Encuentre el número de caracteres diferentes presentes a la derecha del índice actual. Esto se puede hacer restando la frecuencia de ese carácter por el recuento total.
- Ahora agregue este valor calculado a ans , ya que este es el número de caracteres con los que se puede intercambiar el carácter actual para crear una permutación única.
- Ahora, reduzca la frecuencia del carácter actual y cuente por 1, para que no interfiera con los cálculos de los mismos elementos presentes a la derecha.
- Retorna ans+1, porque la string dada también es una permutación única.
C++
// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to calculate total
// number of valid permutations
int validPermutations(string str)
{
unordered_map<char, int> m;
// Creating count which is equal to the
// Total number of characters present and
// ans that will store the number of unique
// permutations
int count = str.length(), ans = 0;
// Storing frequency of each character
// present in the string
for (int i = 0; i < str.length(); i++) {
m[str[i]]++;
}
for (int i = 0; i < str.length(); i++) {
// Adding count of characters by excluding
// characters equal to current char
ans += count - m[str[i]];
// Reduce the frequency of the current character
// and count by 1, so that it cannot interfere
// with the calculations of the same elements
// present to the right of it.
m[str[i]]--;
count--;
}
// Return ans+1 (Because the given string
// is also a unique permutation)
return ans + 1;
}
// Driver Code
int main()
{
string str = "sstt";
cout << validPermutations(str);
return 0;
}
Java
// Java program for the above approach
// Importing HashMap class
import java.util.HashMap;
class GFG {
// Function to calculate total
// number of valid permutations
static int validPermutations(String str)
{
HashMap<Character, Integer> m
= new HashMap<Character, Integer>();
// Creating count which is equal to the
// Total number of characters present and
// ans that will store the number of unique
// permutations
int count = str.length(), ans = 0;
// Storing frequency of each character
// present in the string
for (int i = 0; i < str.length(); i++) {
m.put(str.charAt(i),
m.getOrDefault(str.charAt(i), 0) + 1);
}
for (int i = 0; i < str.length(); i++) {
// Adding count of characters by excluding
// characters equal to current char
ans += count - m.get(str.charAt(i));
// Reduce the frequency of the current character
// and count by 1, so that it cannot interfere
// with the calculations of the same elements
// present to the right of it.
m.put(str.charAt(i), m.get(str.charAt(i)) - 1);
count--;
}
// Return ans+1 (Because the given string
// is also a unique permutation)
return ans + 1;
}
public static void main(String[] args)
{
String str = "sstt";
System.out.println(validPermutations(str));
}
}
// This code is contributed by rajsanghavi9.
Python3
# Python 3 program for the above approach
# Function to calculate total
# number of valid permutations
def validPermutations(str):
m = {}
# Creating count which is equal to the
# Total number of characters present and
# ans that will store the number of unique
# permutations
count = len(str)
ans = 0
# Storing frequency of each character
# present in the string
for i in range(len(str)):
if(str[i] in m):
m[str[i]] += 1
else:
m[str[i]] = 1
for i in range(len(str)):
# Adding count of characters by excluding
# characters equal to current char
ans += count - m[str[i]]
# Reduce the frequency of the current character
# and count by 1, so that it cannot interfere
# with the calculations of the same elements
# present to the right of it.
m[str[i]] -= 1
count -= 1
# Return ans+1 (Because the given string
# is also a unique permutation)
return ans + 1
# Driver Code
if __name__ == '__main__':
str = "sstt"
print(validPermutations(str))
# This code is contributed by SURENDRA_GANGWAR.
C#
// C# program for the above approach
// Importing Dictionary class
using System;
using System.Collections.Generic;
public class GFG {
// Function to calculate total
// number of valid permutations
static int validPermutations(String str)
{
Dictionary<char, int> m
= new Dictionary<char, int>();
// Creating count which is equal to the
// Total number of characters present and
// ans that will store the number of unique
// permutations
int count = str.Length, ans = 0;
// Storing frequency of each character
// present in the string
for (int i = 0; i < str.Length; i++) {
if(m.ContainsKey(str[i]))
m[str[i]]=m[str[i]]+1;
else
m.Add(str[i], 1);
}
for (int i = 0; i < str.Length; i++) {
// Adding count of characters by excluding
// characters equal to current char
ans += count - m[str[i]];
// Reduce the frequency of the current character
// and count by 1, so that it cannot interfere
// with the calculations of the same elements
// present to the right of it.
if(m.ContainsKey(str[i]))
m[str[i]]=m[str[i]]-1;
count--;
}
// Return ans+1 (Because the given string
// is also a unique permutation)
return ans + 1;
}
public static void Main(String[] args)
{
String str = "sstt";
Console.WriteLine(validPermutations(str));
}
}
// This code is contributed by shikhasingrajput
Javascript
<script>
// JavaScript program for the above approach
// Function to calculate total
// number of valid permutations
function validPermutations(str) {
let m = new Map();
// Creating count which is equal to the
// Total number of characters present and
// ans that will store the number of unique
// permutations
let count = str.length,
ans = 0;
// Storing frequency of each character
// present in the string
for (let i = 0; i < str.length; i++) {
if (m.has(str[i])) {
m.set(str[i], m.get(str[i]) + 1);
} else {
m.set(str[i], 1);
}
}
for (let i = 0; i < str.length; i++)
{
// Adding count of characters by excluding
// characters equal to current char
ans += count - m.get(str[i]);
// Reduce the frequency of the current character
// and count by 1, so that it cannot interfere
// with the calculations of the same elements
// present to the right of it.
m.set(str[i], m.get(str[i]) - 1);
count--;
}
// Return ans+1 (Because the given string
// is also a unique permutation)
return ans + 1;
}
// Driver Code
let str = "sstt";
document.write(validPermutations(str));
</script>
Producción:
5
Complejidad de tiempo: O(n)
Espacio Auxiliar: O(n)