Dada una string S y un rango [L, R] . La tarea es encontrar el número de formas en que se puede construir la substring en el rango S[L, R] utilizando los caracteres que existen en la string pero que no se encuentran en el rango S[L, R].
Ejemplos:
Entrada: s = “cabcaab”, l = 1, r = 3
Salida: 2
La substring es “abc”
s[4] + s[6] + s[0] = ‘a’ + ‘b’ + ‘c’ = “abc”
s[5] + s[6] + s[0] = ‘a’ + ‘b’ + ‘c’ = “abc”
Entrada: s = “aaaa”, l = 1, r = 2
Salida : 2
Enfoque: el problema se puede resolver utilizando tablas hash y combinatoria. Se pueden seguir los siguientes pasos para resolver el problema anterior:
- Cuente la frecuencia de cada carácter que no se encuentre en el rango L y R en la tabla hash (por ejemplo, frecuencia).
- Iterar de L a R por separado y calcular el número de formas.
- Para cada carácter en el rango L y R, el número de formas se multiplica por freq[s[i]-‘a’] y disminuye el valor de freq[s[i]-‘a’] en 1.
- En caso de que el valor de freq[s[i]-‘a’] sea 0, no tenemos caracteres para llenar ese lugar, por lo que el número de formas será 0.
- Al final, la multiplicación total será nuestra respuesta.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
// Function to return the number of
// ways to form the sub-string
int calculateWays(string s, int n, int l, int r)
{
// Initialize a hash-table
// with 0
int freq[26];
memset(freq, 0, sizeof freq);
// Iterate in the string and count
// the frequency of characters that
// do not lie in the range L and R
for (int i = 0; i < n; i++) {
// Out of range characters
if (i < l || i > r)
freq[s[i] - 'a']++;
}
// Stores the final number of ways
int ways = 1;
// Iterate for the sub-string in the range
// L and R
for (int i = l; i <= r; i++) {
// If exists then multiply
// the number of ways and
// decrement the frequency
if (freq[s[i] - 'a']) {
ways = ways * freq[s[i] - 'a'];
freq[s[i] - 'a']--;
}
// If does not exist
// the sub-string cannot be formed
else {
ways = 0;
break;
}
}
// Return the answer
return ways;
}
// Driver code
int main()
{
string s = "cabcaab";
int n = s.length();
int l = 1, r = 3;
cout << calculateWays(s, n, l, r);
return 0;
}
Java
// Java implementation of the approach
class GfG {
// Function to return the number of
// ways to form the sub-string
static int calculateWays(String s, int n, int l, int r)
{
// Initialize a hash-table
// with 0
int freq[] = new int[26];
// Iterate in the string and count
// the frequency of characters that
// do not lie in the range L and R
for (int i = 0; i < n; i++) {
// Out of range characters
if (i < l || i > r)
freq[s.charAt(i)-'a']++;
}
// Stores the final number of ways
int ways = 1;
// Iterate for the sub-string in the range
// L and R
for (int i = l; i <= r; i++) {
// If exists then multiply
// the number of ways and
// decrement the frequency
if (freq[s.charAt(i) - 'a'] != 0) {
ways = ways * freq[s.charAt(i) - 'a'];
freq[s.charAt(i) - 'a']--;
}
// If does not exist
// the sub-string cannot be formed
else {
ways = 0;
break;
}
}
// Return the answer
return ways;
}
// Driver code
public static void main(String[] args)
{
String s = "cabcaab";
int n = s.length();
int l = 1, r = 3;
System.out.println(calculateWays(s, n, l, r));
}
}
Python3
# Python 3 implementation of the approach
# Function to return the number of
# ways to form the sub-string
def calculateWays(s, n, l, r):
# Initialize a hash-table
# with 0
freq = [0 for i in range(26)]
# Iterate in the string and count
# the frequency of characters that
# do not lie in the range L and R
for i in range(n):
# Out of range characters
if (i < l or i > r):
freq[ord(s[i]) - ord('a')] += 1
# Stores the final number of ways
ways = 1
# Iterate for the sub-string in the range
# L and R
for i in range(l, r + 1, 1):
# If exists then multiply
# the number of ways and
# decrement the frequency
if (freq[ord(s[i]) - ord('a')]):
ways = ways * freq[ord(s[i]) - ord('a')]
freq[ord(s[i]) - ord('a')] -= 1
# If does not exist
# the sub-string cannot be formed
else:
ways = 0
break
# Return the answer
return ways
# Driver code
if __name__ == '__main__':
s = "cabcaab"
n = len(s)
l = 1
r = 3
print(calculateWays(s, n, l, r))
# This code is contributed by
# Surendra_Gangwar
C#
// C# implementation of the approach
using System;
class GfG
{
// Function to return the number of
// ways to form the sub-string
static int calculateWays(String s, int n, int l, int r)
{
// Initialize a hash-table
// with 0
int []freq = new int[26];
// Iterate in the string and count
// the frequency of characters that
// do not lie in the range L and R
for (int i = 0; i < n; i++)
{
// Out of range characters
if (i < l || i > r)
freq[s[i]-'a']++;
}
// Stores the final number of ways
int ways = 1;
// Iterate for the sub-string in the range
// L and R
for (int i = l; i <= r; i++)
{
// If exists then multiply
// the number of ways and
// decrement the frequency
if (freq[s[i] - 'a'] != 0) {
ways = ways * freq[s[i] - 'a'];
freq[s[i] - 'a']--;
}
// If does not exist
// the sub-string cannot be formed
else {
ways = 0;
break;
}
}
// Return the answer
return ways;
}
// Driver code
public static void Main()
{
String s = "cabcaab";
int n = s.Length;
int l = 1, r = 3;
Console.WriteLine(calculateWays(s, n, l, r));
}
}
/* This code contributed by PrinciRaj1992 */
PHP
<?php
// PHP implementation of the approach
// Function to return the number of
// ways to form the sub-string
function calculateWays($s, $n, $l, $r)
{
// Initialize a hash-table
// with 0
$freq = array();
for($i = 0; $i < 26 ; $i++ )
{
$freq[$i] = 0;
}
// Iterate in the string and count
// the frequency of characters that
// do not lie in the range L and R
for($i = 0; $i < $n ; $i++ )
{
// Out of range characters
if ($i < $l || $i > $r)
$freq[ord($s[$i]) - 97]++;
}
// Stores the final number of ways
$ways = 1;
// Iterate for the sub-string in the range
// L and R
for ($i = $l; $i <= $r; $i++)
{
// If exists then multiply
// the number of ways and
// decrement the frequency
if ($freq[ord($s[$i]) - 97])
{
$ways = $ways * $freq[ord($s[$i]) - 97];
$freq[ord($s[$i]) - 97]--;
}
// If does not exist
// the sub-string cannot be formed
else
{
$ways = 0;
break;
}
}
// Return the answer
return $ways;
}
// Driver code
$s = "cabcaab";
$n = strlen($s);
$l = 1;
$r = 3;
echo calculateWays($s, $n, $l, $r);
// This code is contributed by ihritik
?>
Javascript
<script>
// javascript implementation of the approach
// Function to return the number of
// ways to form the sub-string
function calculateWays( s , n , l , r) {
// Initialize a hash-table
// with 0
var freq = Array(26).fill(0);
// Iterate in the string and count
// the frequency of characters that
// do not lie in the range L and R
for (i = 0; i < n; i++) {
// Out of range characters
if (i < l || i > r)
freq[s.charCodeAt(i) - 'a'.charCodeAt(0)]++;
}
// Stores the final number of ways
var ways = 1;
// Iterate for the sub-string in the range
// L and R
for (i = l; i <= r; i++) {
// If exists then multiply
// the number of ways and
// decrement the frequency
if (freq[s.charCodeAt(i) - 'a'.charCodeAt(0)] != 0) {
ways = ways * freq[s.charCodeAt(i) - 'a'.charCodeAt(0)];
freq[s.charCodeAt(i) - 'a'.charCodeAt(0)]--;
}
// If does not exist
// the sub-string cannot be formed
else {
ways = 0;
break;
}
}
// Return the answer
return ways;
}
// Driver code
var s = "cabcaab";
var n = s.length;
var l = 1, r = 3;
document.write(calculateWays(s, n, l, r));
// This code contributed by umadevi9616
</script>
Producción:
2
Complejidad de tiempo: O(N), donde N es la longitud de la string. Como estamos usando un ciclo para atravesar N veces para obtener las frecuencias de los caracteres presentes en la string.
Espacio auxiliar: O(26), ya que estamos usando espacio adicional para el mapa de frecuencias.