Dados dos números enteros N y K , la tarea es encontrar el número de strings distintas que consisten en alfabetos en minúsculas de longitud N que se pueden formar con como máximo K vocales contiguas. Como la respuesta puede ser demasiado larga, imprima answer%1000000007 .
Entrada: N = 1, K = 0
Salida: 21
Explicación: Todas las 21 consonantes están allí que tienen 0 vocales contiguas y tienen una longitud de 1.Entrada: N = 1, K = 1
Salida: 26
Enfoque: La idea para resolver este problema se basa en la programación dinámica . Siga los pasos a continuación para resolver el problema:
- Sea dp[i][j] el número de formas de hacer distintas strings de longitud i donde los últimos j caracteres de la string son vocales.
- Entonces los estados de la programación dinámica son:
- Si j = 0 , entonces dp[i][j] = (dp[i-1][0] + dp[i-1][1] +……+ dp[i-1][K])*21 (representado por la suma variable entera ) debido a que el último carácter agregado debe ser una consonante, solo el valor de j se convertirá en 0 independientemente de su valor en estados anteriores.
- Si i<j entonces dp[i][j] = 0 . Dado que no es posible crear una string que contenga j vocales y tenga una longitud menor que j .
- Si i == j , entonces dp[i][j] = 5 i porque el número de caracteres en la string es igual al número de vocales, por lo tanto, todos los caracteres deben ser vocales.
- Si j<i , entonces dp[i][j] = dp[i-1][j-1]*5 porque una string de longitud i con los últimos j caracteres vocales solo se puede formar si el último carácter es la vocal y el la string de longitud i-1 tiene el último carácter j – 1 como vocales.
- Imprime la suma de dp[n][0] + dp[n][1] + …… + dp[n][K] como respuesta.
A continuación se muestra la implementación del enfoque anterior.
C++
// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
// Power function to calculate
// long powers with mod
long long int power(long long int x,
long long int y,
long long int p)
{
long long int res = 1ll;
x = x % p;
if (x == 0)
return 0;
while (y > 0) {
if (y & 1)
res = (res * x) % p;
y = y >> 1;
x = (x * x) % p;
}
return res;
}
// Function for finding number of ways to
// create string with length N and atmost
// K contiguous vowels
int kvowelwords(int N, int K)
{
long long int i, j;
long long int MOD = 1000000007;
// Array dp to store number of ways
long long int dp[N + 1][K + 1] = { 0 };
long long int sum = 1;
for (i = 1; i <= N; i++) {
// dp[i][0] = (dp[i-1][0]+dp[i-1][1]..dp[i-1][k])*21
dp[i][0] = sum * 21;
dp[i][0] %= MOD;
// Now setting sum to be dp[i][0]
sum = dp[i][0];
for (j = 1; j <= K; j++) {
// If j>i, no ways are possible to create
// a string with length i and vowel j
if (j > i)
dp[i][j] = 0;
else if (j == i) {
// If j = i all the character should
// be vowel
dp[i][j] = power(5ll, i, MOD);
}
else {
// dp[i][j] relation with dp[i-1][j-1]
dp[i][j] = dp[i - 1][j - 1] * 5;
}
dp[i][j] %= MOD;
// Adding dp[i][j] in the sum
sum += dp[i][j];
sum %= MOD;
}
}
return sum;
}
// Driver Program
int main()
{
// Input
int N = 3;
int K = 3;
// Function Call
cout << kvowelwords(N, K) << endl;
return 0;
}
Java
// Java program for the above approach
class GFG{
// Power function to calculate
// long powers with mod
static int power(int x, int y, int p)
{
int res = 1;
x = x % p;
if (x == 0)
return 0;
while (y > 0)
{
if ((y & 1) != 0)
res = (res * x) % p;
y = y >> 1;
x = (x * x) % p;
}
return res;
}
// Function for finding number of ways to
// create string with length N and atmost
// K contiguous vowels
static int kvowelwords(int N, int K)
{
int i, j;
int MOD = 1000000007;
// Array dp to store number of ways
int[][] dp = new int[N + 1][K + 1] ;
int sum = 1;
for(i = 1; i <= N; i++)
{
// dp[i][0] = (dp[i-1][0]+dp[i-1][1]..dp[i-1][k])*21
dp[i][0] = sum * 21;
dp[i][0] %= MOD;
// Now setting sum to be dp[i][0]
sum = dp[i][0];
for(j = 1; j <= K; j++)
{
// If j>i, no ways are possible to create
// a string with length i and vowel j
if (j > i)
dp[i][j] = 0;
else if (j == i)
{
// If j = i all the character should
// be vowel
dp[i][j] = power(5, i, MOD);
}
else
{
// dp[i][j] relation with dp[i-1][j-1]
dp[i][j] = dp[i - 1][j - 1] * 5;
}
dp[i][j] %= MOD;
// Adding dp[i][j] in the sum
sum += dp[i][j];
sum %= MOD;
}
}
return sum;
}
// Driver Code
public static void main(String[] args)
{
// Input
int N = 3;
int K = 3;
// Function Call
System.out.println( kvowelwords(N, K));
}
}
// This code is contributed by target_2
Python3
# Python3 program for the above approach # Power function to calculate # long powers with mod def power(x, y, p): res = 1 x = x % p if (x == 0): return 0 while (y > 0): if (y & 1): res = (res * x) % p y = y >> 1 x = (x * x) % p return res # Function for finding number of ways to # create string with length N and atmost # K contiguous vowels def kvowelwords(N, K): i, j = 0, 0 MOD = 1000000007 # Array dp to store number of ways dp = [[0 for i in range(K + 1)] for i in range(N + 1)] sum = 1 for i in range(1, N + 1): #dp[i][0] = (dp[i-1][0]+dp[i-1][1]..dp[i-1][k])*21 dp[i][0] = sum * 21 dp[i][0] %= MOD # Now setting sum to be dp[i][0] sum = dp[i][0] for j in range(1, K + 1): # If j>i, no ways are possible to create # a string with length i and vowel j if (j > i): dp[i][j] = 0 elif (j == i): # If j = i all the character should # be vowel dp[i][j] = power(5, i, MOD) else: # dp[i][j] relation with dp[i-1][j-1] dp[i][j] = dp[i - 1][j - 1] * 5 dp[i][j] %= MOD # Adding dp[i][j] in the sum sum += dp[i][j] sum %= MOD return sum # Driver Code if __name__ == '__main__': # Input N = 3 K = 3 # Function Call print (kvowelwords(N, K)) # This code is contributed by mohit kumar 29
C#
// C# program for the above approach
using System;
using System.Collections.Generic;
class GFG{
// Power function to calculate
// long powers with mod
static int power(int x, int y, int p)
{
int res = 1;
x = x % p;
if (x == 0)
return 0;
while (y > 0)
{
if ((y & 1) != 0)
res = (res * x) % p;
y = y >> 1;
x = (x * x) % p;
}
return res;
}
// Function for finding number of ways to
// create string with length N and atmost
// K contiguous vowels
static int kvowelwords(int N, int K)
{
int i, j;
int MOD = 1000000007;
// Array dp to store number of ways
int[,] dp = new int[N + 1, K + 1];
int sum = 1;
for(i = 1; i <= N; i++)
{
// dp[i][0] = (dp[i-1, 0]+dp[i-1, 1]..dp[i-1][k])*21
dp[i, 0] = sum * 21;
dp[i, 0] %= MOD;
// Now setting sum to be dp[i][0]
sum = dp[i, 0];
for(j = 1; j <= K; j++)
{
// If j>i, no ways are possible to create
// a string with length i and vowel j
if (j > i)
dp[i, j] = 0;
else if (j == i)
{
// If j = i all the character should
// be vowel
dp[i, j] = power(5, i, MOD);
}
else
{
// dp[i][j] relation with dp[i-1][j-1]
dp[i, j] = dp[i - 1, j - 1] * 5;
}
dp[i, j] %= MOD;
// Adding dp[i][j] in the sum
sum += dp[i, j];
sum %= MOD;
}
}
return sum;
}
// Driver Code
public static void Main()
{
// Input
int N = 3;
int K = 3;
// Function Call
Console.Write(kvowelwords(N, K));
}
}
// This code is contributed by code_hunt
Javascript
<script>
// JavaScript code for above approach
// Power function to calculate
// long powers with mod
function power(x, y, p)
{
let res = 1;
x = x % p;
if (x == 0)
return 0;
while (y > 0)
{
if ((y & 1) != 0)
res = (res * x) % p;
y = y >> 1;
x = (x * x) % p;
}
return res;
}
// Function for finding number of ways to
// create string with length N and atmost
// K contiguous vowels
function kvowelwords(N, K)
{
let i, j;
let MOD = 1000000007;
// Array dp to store number of ways
let dp = new Array(N + 1)
// Loop to create 2D array using 1D array
for (i = 0; i < dp.length; i++) {
dp[i] = new Array(K + 1);
}
let sum = 1;
for(i = 1; i <= N; i++)
{
// dp[i][0] = (dp[i-1][0]+dp[i-1][1]..dp[i-1][k])*21
dp[i][0] = sum * 21;
dp[i][0] %= MOD;
// Now setting sum to be dp[i][0]
sum = dp[i][0];
for(j = 1; j <= K; j++)
{
// If j>i, no ways are possible to create
// a string with length i and vowel j
if (j > i)
dp[i][j] = 0;
else if (j == i)
{
// If j = i all the character should
// be vowel
dp[i][j] = power(5, i, MOD);
}
else
{
// dp[i][j] relation with dp[i-1][j-1]
dp[i][j] = dp[i - 1][j - 1] * 5;
}
dp[i][j] %= MOD;
// Adding dp[i][j] in the sum
sum += dp[i][j];
sum %= MOD;
}
}
return sum;
}
// Driver Code
// Input
let N = 3;
let K = 3;
// Function Call
document.write( kvowelwords(N, K));
// This code is contributed by sanjoy_62.
</script>
Producción:
17576
Complejidad temporal: O(N×K)
Espacio auxiliar: O(N×K)