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>
1
Complejidad temporal: O(N)
Complejidad espacial auxiliar: O(N)