Given a string S of size N consisting of digits and ?, the task is to find the number of strings formed such that replacing the character ‘?’ with any digits such that the digits of the string become non-decreasing.
Examples:
Input: S = “1???2”
Output: 4
Explanation:
The string after valid replacements of ‘?’ is 11112, 11122, 11222, 12222. Therefore, the count of such string is 1.Input: S = “2??43?4”
Output: 0
Approach: The given problem can be solved by replacing ‘?’ with all possible valid combinations of digits using recursion and store the Overlapping Subproblems in the dp[] table. Follow the steps below to solve the given problem:
- Initialize a 2D array, say dp[][] such that dp[i][j] will denote the possible number of valid strings having the length i and between two numbers whose endpoint difference is j. As the different segments containing ? are independent of each other. So the total count will be the product of all the choices available for each segment.
- Initialize the dp[][] as -1.
- Declare three variables L as 0, R as 9, cnt, such that L denotes the left limit of the segment, R denotes the right limit of the segment, and cnt denotes the length of contiguous ‘?’ characters.
- Let the total count be stored in the variable, say ans as 1.
- Define a function solve that will calculate the values of dp nodes recursively. The solve function will take two arguments (len, gap), len will denote the total length of continuous ‘?’ and the gap will denote the difference between endpoints of that segment as:
- Iterate for each possible gap and recalculate the answer with solve(len – 1, gap – i).
- Return the answer obtained from solve function after filling the node dp[len][gap].
- Iterate through each character in the string and perform the following steps:
- If the current character is ‘?’ then increments the variable cnt.
- If the current character is not a number change the Right limit i.e., R to the current character, i.e., R = S[i] – ‘0’.
- Multiply the answer calculated by the recursive function solve(cnt, R – L).
- After completing the above steps, print the value of ans as the resultant count of strings formed.
Below is the implementation of the above approach:
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;#define MAXN 100005// Define the dp table globallyint dp[MAXN][10];// Recursive function to calculate total// number of valid non-decreasing stringsint solve(int len, int gap){ // If already calculated state if (dp[len][gap] != -1) { return dp[len][gap]; } // Base Case if (len == 0 || gap == 0) { return 1; } if (gap < 0) { return 0; } // Stores the total count of strings // formed int ans = 0; for (int i = 0; i <= gap; i++) { ans += solve(len - 1, gap - i); } // Fill the value in dp matrix return dp[len][gap] = ans;}// Function to find the total number of// non-decreasing string formed by// replacing the '?'int countValidStrings(string S){ // Initialize all value of dp // table with -1 memset(dp, -1, sizeof(dp)); int N = S.length(); // Left and Right limits int L = 1, R = 9; int cnt = 0; int ans = 1; // Iterate through all the characters // of the string S for (int i = 0; i < N; i++) { if (S[i] != '?') { // Change R to the current // character R = S[i] - '0'; // Call the recursive function ans *= solve(cnt, R - L); // Change L to R and R to 9 L = R; R = 9; // Reinitialize the length // of ? to 0 cnt = 0; } else { // Increment the length of // the segment cnt++; } } // Update the ans ans *= solve(cnt, R - L); // Return the total count return ans;}// Driver Codeint main(){ string S = "1???2"; cout << countValidStrings(S); return 0;} |
Java
// Java program for the above approachimport java.io.*;class GFG { static final int MAXN = 100005; // Define the dp table globally static final int dp[][] = new int[MAXN][10]; // Recursive function to calculate total // number of valid non-decreasing strings static int solve(int len, int gap) { // If already calculated state if (dp[len][gap] != -1) { return dp[len][gap]; } // Base Case if (len == 0 || gap == 0) { return 1; } if (gap < 0) { return 0; } // Stores the total count of strings // formed int ans = 0; for (int i = 0; i <= gap; i++) { ans += solve(len - 1, gap - i); } // Fill the value in dp matrix return dp[len][gap] = ans; } // Function to find the total number of // non-decreasing string formed by // replacing the '?' static int countValidStrings(String S) { // Initialize all value of dp // table with -1 for (int i = 0; i < MAXN; i++) { for (int j = 0; j < 10; j++) { dp[i][j] = -1; } } int N = S.length(); // Left and Right limits int L = 1, R = 9; int cnt = 0; int ans = 1; // Iterate through all the characters // of the string S for (int i = 0; i < N; i++) { if (S.charAt(i) != '?') { // Change R to the current // character R = S.charAt(i) - '0'; // Call the recursive function ans *= solve(cnt, R - L); // Change L to R and R to 9 L = R; R = 9; // Reinitialize the length // of ? to 0 cnt = 0; } else { // Increment the length of // the segment cnt++; } } // Update the ans ans *= solve(cnt, R - L); // Return the total count return ans; } // Driver Code public static void main(String[] args) { String S = "1???2"; System.out.println(countValidStrings(S)); }}// This code is contributed by Dharanendra L V. |
Python3
# Python 3 program for the above approachMAXN = 100005# Define the dp table globallydp = [[-1 for x in range(10)] for y in range(MAXN)]# Recursive function to calculate total# number of valid non-decreasing stringsdef solve(len, gap): # If already calculated state if (dp[len][gap] != -1): return dp[len][gap] # Base Case if (len == 0 or gap == 0): return 1 if (gap < 0): return 0 # Stores the total count of strings # formed ans = 0 for i in range(gap + 1): ans += solve(len - 1, gap - i) # Fill the value in dp matrix dp[len][gap] = ans return dp[len][gap]# Function to find the total number of# non-decreasing string formed by# replacing the '?'def countValidStrings(S): # Initialize all value of dp # table with -1 global dp N = len(S) # Left and Right limits L, R = 1, 9 cnt = 0 ans = 1 # Iterate through all the characters # of the string S for i in range(N): if (S[i] != '?'): # Change R to the current # character R = ord(S[i]) - ord('0') # Call the recursive function ans *= solve(cnt, R - L) # Change L to R and R to 9 L = R R = 9 # Reinitialize the length # of ? to 0 cnt = 0 else: # Increment the length of # the segment cnt += 1 # Update the ans ans *= solve(cnt, R - L) # Return the total count return ans# Driver Codeif __name__ == "__main__": S = "1???2" print(countValidStrings(S)) # This code is contributed by ukasp. |
C#
// C# program for the above approachusing System;using System.Collections.Generic;class GFG{static int MAXN = 100005;// Define the dp table globallystatic int [,]dp = new int[MAXN, 10];// Recursive function to calculate total// number of valid non-decreasing stringsstatic int solve(int len, int gap){ // If already calculated state if (dp[len,gap] != -1) { return dp[len,gap]; } // Base Case if (len == 0 || gap == 0) { return 1; } if (gap < 0) { return 0; } // Stores the total count of strings // formed int ans = 0; for (int i = 0; i <= gap; i++) { ans += solve(len - 1, gap - i); } // Fill the value in dp matrix return dp[len,gap] = ans;}// Function to find the total number of// non-decreasing string formed by// replacing the '?'static int countValidStrings(string S){ // Initialize all value of dp // table with -1 for(int i = 0; i < MAXN; i++){ for(int j = 0; j < 10; j++){ dp[i, j] = -1; } } int N = S.Length; // Left and Right limits int L = 1, R = 9; int cnt = 0; int ans = 1; // Iterate through all the characters // of the string S for (int i = 0; i < N; i++) { if (S[i] != '?') { // Change R to the current // character R = (int)S[i] - 48; // Call the recursive function ans *= solve(cnt, R - L); // Change L to R and R to 9 L = R; R = 9; // Reinitialize the length // of ? to 0 cnt = 0; } else { // Increment the length of // the segment cnt++; } } // Update the ans ans *= solve(cnt, R - L); // Return the total count return ans;}// Driver Codepublic static void Main(){ string S = "1???2"; Console.Write(countValidStrings(S));}}// This code is contributed by SURENDR_GANGWAR. |
Javascript
<script> // JavaScript Program to implement // the above approach let MAXN = 100005 // Define the dp table globally let dp = new Array(MAXN).fill(new Array(10)); // Recursive function to calculate total // number of valid non-decreasing strings function solve(len, gap) { // If already calculated state if (dp[len][gap] != -1) { return dp[len][gap]; } // Base Case if (len == 0 || gap == 0) { return 1; } if (gap < 0) { return 0; } // Stores the total count of strings // formed let ans = 0; for (let i = 0; i <= gap; i++) { ans += solve(len - 1, gap - i); } // Fill the value in dp matrix return dp[len][gap] = ans; } // Function to find the total number of // non-decreasing string formed by // replacing the '?' function countValidStrings(S) { // Initialize all value of dp // table with -1 for (let i = 0; i < dp.length; i++) { for (let j = 0; j < dp[i].length; j++) { dp[i][j] = -1; } } let N = S.length; // Left and Right limits let L = 1, R = 9; let cnt = 0; let ans = 1; // Iterate through all the characters // of the string S for (let i = 0; i < N; i++) { if (S[i] != '?') { // Change R to the current // character R = S.charCodeAt(i) - '0'.charCodeAt(0); // Call the recursive function ans *= solve(cnt, R - L); // Change L to R and R to 9 L = R; R = 9; // Reinitialize the length // of ? to 0 cnt = 0; } else { // Increment the length of // the segment cnt++; } } // Update the ans ans *= solve(cnt, R - L); // Return the total count return ans; } // Driver Code let S = "1???2"; document.write(countValidStrings(S)); // This code is contributed by Potta Lokesh </script> |
Output
4
Time Complexity: O(N*10)
Auxiliary Space: O(N*10)
Efficient approach : Using DP Tabulation method ( Iterative approach )
The approach to solve this problem is same but DP tabulation(bottom-up) method is better then Dp + memoization(top-down) because memoization method needs extra stack space of recursion calls.
Steps to solve this problem :
- Create a DP of size ( len * gap) to store the solution of the subproblems and initlaize it with 0.
- Initialize the DP with base cases
- Now Iterate over subproblems to get the value of current problem form previous computation of subproblems stored in DP
- Return the final solution stored in dp[len][gap].
Implementation :
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;#define MAXN 100005// Define the dp table globallyint dp[MAXN][10];// Recursive function to calculate total// number of valid non-decreasing stringsint solve(int len, int gap) { int dp[len + 1][gap + 1]; memset(dp, 0, sizeof(dp)); // Base cases for (int i = 0; i <= len; i++) { dp[i][0] = 1; } for (int i = 1; i <= gap; i++) { dp[0][i] = 1; } for (int i = 1; i <= len; i++) { for (int j = 1; j <= gap; j++) { for (int k = 0; k <= j; k++) { dp[i][j] += dp[i - 1][j - k]; } } } return dp[len][gap];}// Function to find the total number of// non-decreasing string formed by// replacing the '?'int countValidStrings(string S){ // Initialize all value of dp // table with -1 memset(dp, -1, sizeof(dp)); int N = S.length(); // Left and Right limits int L = 1, R = 9; int cnt = 0; int ans = 1; // Iterate through all the characters // of the string S for (int i = 0; i < N; i++) { if (S[i] != '?') { // Change R to the current // character R = S[i] - '0'; // Call the recursive function ans *= solve(cnt, R - L); // Change L to R and R to 9 L = R; R = 9; // Reinitialize the length // of ? to 0 cnt = 0; } else { // Increment the length of // the segment cnt++; } } // Update the ans ans *= solve(cnt, R - L); // Return the total count return ans;}// Driver Codeint main(){ string S = "1???2"; cout << countValidStrings(S); return 0;} |
Java
import java.util.*;public class Main { static int MAXN = 100005; // Define the dp table globally static int[][] dp = new int[MAXN][10]; // Recursive function to calculate total // number of valid non-decreasing strings static int solve(int len, int gap) { int[][] dp = new int[len + 1][gap + 1]; for (int[] row : dp) { Arrays.fill(row, 0); } // Base cases for (int i = 0; i <= len; i++) { dp[i][0] = 1; } for (int i = 1; i <= gap; i++) { dp[0][i] = 1; } for (int i = 1; i <= len; i++) { for (int j = 1; j <= gap; j++) { for (int k = 0; k <= j; k++) { dp[i][j] += dp[i - 1][j - k]; } } } return dp[len][gap]; } // Function to find the total number of // non-decreasing string formed by // replacing the '?' static int countValidStrings(String S) { // Initialize all value of dp // table with -1 for (int[] row : dp) { Arrays.fill(row, -1); } int N = S.length(); // Left and Right limits int L = 1, R = 9; int cnt = 0; int ans = 1; // Iterate through all the characters // of the string S for (int i = 0; i < N; i++) { if (S.charAt(i) != '?') { // Change R to the current // character R = S.charAt(i) - '0'; // Call the recursive function ans *= solve(cnt, R - L); // Change L to R and R to 9 L = R; R = 9; // Reinitialize the length // of ? to 0 cnt = 0; } else { // Increment the length of // the segment cnt++; } } // Update the ans ans *= solve(cnt, R - L); // Return the total count return ans; } // Driver Code public static void main(String[] args) { String S = "1???2"; System.out.println(countValidStrings(S)); }} |
Python
MAXN = 100005# Define the dp table globallydp = [[-1 for i in range(10)] for j in range(MAXN)]# Recursive function to calculate total# number of valid non-decreasing stringsdef solve(len, gap): dp = [[0 for i in range(gap + 1)] for j in range(len + 1)] # Base cases for i in range(len + 1): dp[i][0] = 1 for i in range(1, gap + 1): dp[0][i] = 1 for i in range(1, len + 1): for j in range(1, gap + 1): for k in range(j + 1): dp[i][j] += dp[i - 1][j - k] return dp[len][gap]# Function to find the total number of# non-decreasing string formed by# replacing the '?'def countValidStrings(S): global dp N = len(S) # Left and Right limits L = 1 R = 9 cnt = 0 ans = 1 # Iterate through all the characters # of the string S for i in range(N): if S[i] != '?': # Change R to the current # character R = ord(S[i]) - ord('0') # Call the recursive function ans *= solve(cnt, R - L) # Change L to R and R to 9 L = R R = 9 # Reinitialize the length # of ? to 0 cnt = 0 else: # Increment the length of # the segment cnt += 1 # Update the ans ans *= solve(cnt, R - L) # Return the total count return ans# Driver Codeif __name__ == '__main__': S = "1???2" print(countValidStrings(S)) |
C#
using System;class Program{ // Recursive function to calculate the total // number of valid non-decreasing strings static int Solve(int len, int gap) { int[,] dp = new int[len + 1, gap + 1]; // Initialize dp with zeros for (int i = 0; i <= len; i++) { dp[i, 0] = 1; } for (int i = 1; i <= gap; i++) { dp[0, i] = 1; } for (int i = 1; i <= len; i++) { for (int j = 1; j <= gap; j++) { for (int k = 0; k <= j; k++) { dp[i, j] += dp[i - 1, j - k]; } } } return dp[len, gap]; } // Function to find the total number of // non-decreasing strings formed by // replacing the '?' static int CountValidStrings(string S) { int N = S.Length; // Left and Right limits int L = 1, R = 9; int cnt = 0; int ans = 1; // Iterate through all the characters // of the string S for (int i = 0; i < N; i++) { if (S[i] != '?') { // Change R to the current character R = S[i] - '0'; // Call the recursive function ans *= Solve(cnt, R - L); // Change L to R and R to 9 L = R; R = 9; // Reinitialize the length of ? to 0 cnt = 0; } else { // Increment the length of the segment cnt++; } } // Update the ans ans *= Solve(cnt, R - L); // Return the total count return ans; } // Driver Code static void Main() { string S = "1???2"; Console.WriteLine(CountValidStrings(S)); }} |
Javascript
function solve(len, gap) { let dp = new Array(len + 1).fill().map(() => new Array(gap + 1).fill(0)); // Base cases for (let i = 0; i <= len; i++) { dp[i][0] = 1; } for (let i = 1; i <= gap; i++) { dp[0][i] = 1; } for (let i = 1; i <= len; i++) { for (let j = 1; j <= gap; j++) { for (let k = 0; k <= j; k++) { dp[i][j] += dp[i - 1][j - k]; } } } return dp[len][gap];}function countValidStrings(S) { let N = S.length; // Left and Right limits let L = 1, R = 9; let cnt = 0; let ans = 1; // Iterate through all the characters // of the string S for (let i = 0; i < N; i++) { if (S[i] != '?') { // Change R to the current // character R = parseInt(S[i]); // Call the recursive function ans *= solve(cnt, R - L); // Change L to R and R to 9 L = R; R = 9; // Reinitialize the length // of ? to 0 cnt = 0; } else { // Increment the length of // the segment cnt++; } } // Update the ans ans *= solve(cnt, R - L); // Return the total count return ans;}// Driver Codelet S = "1???2";console.log(countValidStrings(S)); |
Output:
4
Time Complexity: O(N*10)
Auxiliary Space: O(N*10)
