Dado un gran número en forma de string str de tamaño N , la tarea es contar la subsecuencia de longitud 4 cuyos dígitos tienen la forma de (x, x, x+1, x+1) .
Ejemplo:
Entrada: str = «1515732322»
Salida: 3
Explicación:
Para la string de entrada dada str = «1515732322», hay 3 subsecuencias {1122}, {1122} y {1122} que están en la forma dada de (x, x , x+1, x+1).Entrada: str = “224353”
Salida: 1
Explicación:
Para la string de entrada dada str = “224353”, solo hay 1 subsecuencia posible {2233} en la forma dada de (x, x, x+1, x+1) .
Enfoque de la suma de prefijos: Consulte el Conjunto 1 para conocer el enfoque de la suma de prefijos .
Enfoque de programación dinámica: este problema se puede resolver utilizando la programación dinámica .
Usaremos 2 arrays como count1[][j] y count2[][10] de modo que count1[i][10] almacenará el recuento de elementos iguales consecutivos del dígito j en el índice actual i atravesando la string desde la izquierda y count2 [i][j] almacenará el recuento de elementos iguales consecutivos del dígito j en el índice actual i que atraviesa la string desde la derecha. A continuación se muestran los pasos:
- Inicialice la array de dos recuentos count1[][10] para llenar la tabla de izquierda a derecha y count2[][10] para llenar la tabla de derecha a izquierda de la string de entrada.
- Atraviese la string de entrada y llene la array count1 y count2.
- La relación de recurrencia para count1[][] viene dada por:
cuenta1[i][j] += cuenta1[i – 1][j]
donde cuenta1[i][j] es la cuenta de dos adyacentes en el índice i para el dígito j
- La relación de recurrencia para count2[][] viene dada por:
cuenta2[i][j] += cuenta1[i + 1][j]
donde cuenta2[i][j] es la cuenta de dos adyacentes en el índice i para el dígito j
- Inicialice una respuesta variable a 0 que almacene el recuento resultante de números estables.
- Atraviese la string de entrada y obtenga el recuento de números de la array count1[][] y count2[][] de modo que la diferencia entre el número de count1[][] y la array count2[][] sea 1 y almacénelo en la variable c1 y c2.
- Finalmente actualice result(say ans ) con (c1 * ((c2 * (c2 – 1) / 2))) .
- Imprima la respuesta calculada arriba.
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;
// Function to count the numbers
int countStableNum(string str, int N)
{
// Array that stores the
// digits from left to right
int count1[N][10];
// Array that stores the
// digits from right to left
int count2[N][10];
// Initially both array store zero
for (int i = 0; i < N; i++)
for (int j = 0; j < 10; j++)
count1[i][j] = count2[i][j] = 0;
// Fill the table for count1 array
for (int i = 0; i < N; i++) {
if (i != 0) {
for (int j = 0; j < 10; j++) {
count1[i][j] += count1[i - 1][j];
}
}
// Update the count of current character
count1[i][str[i] - '0']++;
}
// Fill the table for count2 array
for (int i = N - 1; i >= 0; i--) {
if (i != N - 1) {
for (int j = 0; j < 10; j++) {
count2[i][j] += count2[i + 1][j];
}
}
// Update the count of cuuent character
count2[i][str[i] - '0']++;
}
// Variable that stores the
// count of the numbers
int ans = 0;
// Traverse Input string and get the
// count of digits from count1 and
// count2 array such that difference
// b/w digit is 1 & store it int c1 &c2.
// And store it in variable c1 and c2
for (int i = 1; i < N - 1; i++) {
if (str[i] == '9')
continue;
int c1 = count1[i - 1][str[i] - '0'];
int c2 = count2[i + 1][str[i] - '0' + 1];
if (c2 == 0)
continue;
// Update the ans
ans = (ans
+ (c1 * ((c2 * (c2 - 1) / 2))));
}
// Return the final count
return ans;
}
// Driver Code
int main()
{
// Given String
string str = "224353";
int N = str.length();
// Function Call
cout << countStableNum(str, N);
return 0;
}
Java
// Java program for the above approach
import java.io.*;
class GFG{
// Function to count the numbers
static int countStableNum(String str, int N)
{
// Array that stores the
// digits from left to right
int count1[][] = new int[N][10];
// Array that stores the
// digits from right to left
int count2[][] = new int[N][10];
// Initially both array store zero
for(int i = 0; i < N; i++)
for(int j = 0; j < 10; j++)
count1[i][j] = count2[i][j] = 0;
// Fill the table for count1 array
for(int i = 0; i < N; i++)
{
if (i != 0)
{
for(int j = 0; j < 10; j++)
{
count1[i][j] += count1[i - 1][j];
}
}
// Update the count of current character
count1[i][str.charAt(i) - '0']++;
}
// Fill the table for count2 array
for(int i = N - 1; i >= 0; i--)
{
if (i != N - 1)
{
for(int j = 0; j < 10; j++)
{
count2[i][j] += count2[i + 1][j];
}
}
// Update the count of cuuent character
count2[i][str.charAt(i) - '0']++;
}
// Variable that stores the
// count of the numbers
int ans = 0;
// Traverse Input string and get the
// count of digits from count1 and
// count2 array such that difference
// b/w digit is 1 & store it int c1 &c2.
// And store it in variable c1 and c2
for(int i = 1; i < N - 1; i++)
{
if (str.charAt(i) == '9')
continue;
int c1 = count1[i - 1][str.charAt(i) - '0'];
int c2 = count2[i + 1][str.charAt(i) - '0' + 1];
if (c2 == 0)
continue;
// Update the ans
ans = (ans + (c1 * ((c2 * (c2 - 1) / 2))));
}
// Return the final count
return ans;
}
// Driver code
public static void main(String[] args)
{
// Given String
String str = "224353";
int N = str.length();
// Function call
System.out.println(countStableNum(str, N));
}
}
// This code is contributed by Pratima Pandey
Python3
# Python3 program for the above approach
# Function to count the numbers
def countStableNum(Str, N):
# Array that stores the
# digits from left to right
count1 = [[0 for j in range(10)]
for i in range(N)]
# Array that stores the
# digits from right to left
count2 = [[0 for j in range(10)]
for i in range(N)]
# Initially both array store zero
for i in range(N):
for j in range(10):
count1[i][j], count2[i][j] = 0, 0
# Fill the table for count1 array
for i in range(N):
if (i != 0):
for j in range(10):
count1[i][j] = (count1[i][j] +
count1[i - 1][j])
# Update the count of current character
count1[i][ord(Str[i]) - ord('0')] += 1
# Fill the table for count2 array
for i in range(N - 1, -1, -1):
if (i != N - 1):
for j in range(10):
count2[i][j] += count2[i + 1][j]
# Update the count of cuuent character
count2[i][ord(Str[i]) -
ord('0')] = count2[i][ord(Str[i]) -
ord('0')] + 1
# Variable that stores the
# count of the numbers
ans = 0
# Traverse Input string and get the
# count of digits from count1 and
# count2 array such that difference
# b/w digit is 1 & store it int c1 &c2.
# And store it in variable c1 and c2
for i in range(1, N - 1):
if (Str[i] == '9'):
continue
c1 = count1[i - 1][ord(Str[i]) - ord('0')]
c2 = count2[i + 1][ord(Str[i]) - ord('0') + 1]
if (c2 == 0):
continue
# Update the ans
ans = (ans + (c1 * ((c2 * (c2 - 1) // 2))))
# Return the final count
return ans
# Driver code
# Given String
Str = "224353"
N = len(Str)
# Function call
print(countStableNum(Str, N))
# This code is contributed by divyeshrabadiya07
C#
// C# program for the above approach
using System;
class GFG{
// Function to count the numbers
static int countStableNum(String str, int N)
{
// Array that stores the
// digits from left to right
int [,]count1 = new int[N, 10];
// Array that stores the
// digits from right to left
int [,]count2 = new int[N, 10];
// Initially both array store zero
for(int i = 0; i < N; i++)
for(int j = 0; j < 10; j++)
count1[i, j] = count2[i, j] = 0;
// Fill the table for count1 array
for(int i = 0; i < N; i++)
{
if (i != 0)
{
for(int j = 0; j < 10; j++)
{
count1[i, j] += count1[i - 1, j];
}
}
// Update the count of current character
count1[i, str[i] - '0']++;
}
// Fill the table for count2 array
for(int i = N - 1; i >= 0; i--)
{
if (i != N - 1)
{
for(int j = 0; j < 10; j++)
{
count2[i, j] += count2[i + 1, j];
}
}
// Update the count of cuuent character
count2[i, str[i] - '0']++;
}
// Variable that stores the
// count of the numbers
int ans = 0;
// Traverse Input string and get the
// count of digits from count1 and
// count2 array such that difference
// b/w digit is 1 & store it int c1 &c2.
// And store it in variable c1 and c2
for(int i = 1; i < N - 1; i++)
{
if (str[i] == '9')
continue;
int c1 = count1[i - 1, str[i] - '0'];
int c2 = count2[i + 1, str[i] - '0' + 1];
if (c2 == 0)
continue;
// Update the ans
ans = (ans + (c1 * ((c2 * (c2 - 1) / 2))));
}
// Return the readonly count
return ans;
}
// Driver code
public static void Main(String[] args)
{
// Given String
String str = "224353";
int N = str.Length;
// Function call
Console.WriteLine(countStableNum(str, N));
}
}
// This code is contributed by Amit Katiyar
Javascript
<script>
// Javascript program for the above approach
// Function to count the numbers
function countStableNum(str, N)
{
// Array that stores the
// digits from left to right
var count1 = Array.from(Array(N), ()=>Array(10));
// Array that stores the
// digits from right to left
var count2 = Array.from(Array(N), ()=>Array(10));
// Initially both array store zero
for (var i = 0; i < N; i++)
for (var j = 0; j < 10; j++)
count1[i][j] = count2[i][j] = 0;
// Fill the table for count1 array
for (var i = 0; i < N; i++) {
if (i != 0) {
for (var j = 0; j < 10; j++) {
count1[i][j] += count1[i - 1][j];
}
}
// Update the count of current character
count1[i][str[i] - '0']++;
}
// Fill the table for count2 array
for (var i = N - 1; i >= 0; i--) {
if (i != N - 1) {
for (var j = 0; j < 10; j++) {
count2[i][j] += count2[i + 1][j];
}
}
// Update the count of cuuent character
count2[i][str[i] - '0']++;
}
// Variable that stores the
// count of the numbers
var ans = 0;
// Traverse Input string and get the
// count of digits from count1 and
// count2 array such that difference
// b/w digit is 1 & store it var c1 &c2.
// And store it in variable c1 and c2
for (var i = 1; i < N - 1; i++) {
if (str[i] == '9')
continue;
var c1 = count1[i - 1][str[i] - '0'];
var c2 = count2[i + 1][str[i] - '0' + 1];
if (c2 == 0)
continue;
// Update the ans
ans = (ans
+ (c1 * ((c2 * (c2 - 1) / 2))));
}
// Return the final count
return ans;
}
// Driver Code
// Given String
var str = "224353";
var N = str.length;
// Function Call
document.write( countStableNum(str, N));
</script>
Producción:
1
Complejidad temporal: O(N)
Complejidad espacial auxiliar: O(N)