Given a binary string str of size N containing 0 and 1 only, the task is to count all possible distinct binary strings when a substring “11” can be replaced by “0”.
Examples:
Input: str = “11011”
Output: 4
Explanation: All possible combinations are “11011”, “0011”, “1100”, “000”.Input: str = “110011100011111”
Output: 48
Naive Approach: The simplest idea to solve the problem is to try changing every possible substring and find out total how many distinct strings are being formed.
Time Complexity: O(2N)
Auxiliary Space: O(2N)
Efficient Approach: This problem can be efficiently solved by using the concept of dynamic programming with the help of the following idea:
- Consider there are X number of groups of consecutive 1s. Find out in how many ways each of these groups can be modified by changing “11” to “0”. The multiplication of all those values will be the required answer.
- Dynamic programming (say dp[] array) can be used to find the possible combinations of consecutive 1s.
- If the ith element is 0, it cannot be changed. So dp[i] = 1.
- If ith character is 1 it can be kept 1 in dp[i-1] ways or (i-1)th and ith character can be replaced with 0 in dp[i-2] ways.
So dp[i] = dp[i-1]+dp[i-2] in this case
Follow the steps mentioned below to solve the problem:
- Iterate from i = 0 to N-1 and use the above observation to fill the dp[] array.
- Again iterate from the starting and multiply the number of combinations of the consecutive 1s.
- Return the multiplied value as the answer.
Below is the implementation of the above approach.
C++
// C++ code to implement above approach #include <bits/stdc++.h> using namespace std; // Function to return the // total different combination // possible int total_count(string s, int n) { int ans = 1, dp[n] = { 0 }; // Base cases if (s[0] == '1' ) dp[0] = 1; if (s[1] == '1' && s[1] == s[0]) { dp[1] = 2; } else if (s[1] == '1' ) { dp[1] = 1; } // Iterating through every index // and storing the total // combination of string due to // all the adjacent 1's. for ( int i = 2; i < n; i++) { if (s[i] == '1' ) { if (s[i] == s[i - 1]) { if (s[i - 1] == s[i - 2]) { dp[i] = dp[i - 1] + dp[i - 2]; } else { dp[i] = 2; } } else { dp[i] = 1; } } } // Total combinations possible // by multiplying all the individual // combinations. for ( int i = 1; i < n; i++) { if (dp[i - 1] > dp[i]) { ans = ans * dp[i - 1]; } } // Edge case if (dp[n - 1] != 0) { ans = ans * dp[n - 1]; } // Returning the final value return ans; } // Driver code int main() { string str = "11011" ; int N; N = str.size(); // Function call cout << total_count(str, N); return 0; } |
Java
// JAVA code to implement above approach import java.util.*; class GFG { // Function to return the // total different combination // possible public static int total_count(String s, int n) { int ans = 1 ; int dp[] = new int [n]; for ( int i = 0 ; i < n; ++i) { dp[i] = 0 ; } // Base cases if (s.charAt( 0 ) == '1' ) dp[ 0 ] = 1 ; if (s.charAt( 1 ) == '1' && s.charAt( 1 ) == s.charAt( 0 )) { dp[ 1 ] = 2 ; } else if (s.charAt( 1 ) == '1' ) { dp[ 1 ] = 1 ; } // Iterating through every index // and storing the total // combination of string due to // all the adjacent 1's. for ( int i = 2 ; i < n; i++) { if (s.charAt(i) == '1' ) { if (s.charAt(i) == s.charAt(i - 1 )) { if (s.charAt(i - 1 ) == s.charAt(i - 2 )) { dp[i] = dp[i - 1 ] + dp[i - 2 ]; } else { dp[i] = 2 ; } } else { dp[i] = 1 ; } } } // Total combinations possible // by multiplying all the individual // combinations. for ( int i = 1 ; i < n; i++) { if (dp[i - 1 ] > dp[i]) { ans = ans * dp[i - 1 ]; } } // Edge case if (dp[n - 1 ] != 0 ) { ans = ans * dp[n - 1 ]; } // Returning the final value return ans; } // Driver code public static void main(String[] args) { String str = "11011" ; int N; N = str.length(); // Function call System.out.print(total_count(str, N)); } } // This code is contributed by Taranpreet |
Python3
# Python3 code to implement the above approach # function to return the total different # combination possible def total_count(s, n): ans = 1 dp = [ 0 ] * n # base cases if s[ 0 ] = = "1" : dp[ 0 ] = 1 if s[ 1 ] = = "1" and s[ 1 ] = = s[ 0 ]: dp[ 1 ] = 2 elif s[ 1 ] = = "1" : dp[ 1 ] = 1 # iterating through every index and storing # the total combination of strings due to all # the adjacent 1s for i in range ( 2 , n): if s[i] = = "1" : if s[i] = = s[i - 1 ]: if s[i - 1 ] = = s[i - 2 ]: dp[i] = dp[i - 1 ] + dp[i - 2 ] else : dp[i] = 2 else : dp[i] = 1 # Total combinations possible by multiplying # all the individual combinations for i in range ( 1 , n): if dp[i - 1 ] > dp[i]: ans * = dp[i - 1 ] # Edge case if dp[n - 1 ] ! = 0 : ans * = dp[n - 1 ] # Returning the final value return ans # Driver Code string = "11011" N = len (string) # Function Call print (total_count(string, N)) #This Code was contributed by phasing17 |
C#
// C# code to implement above approach using System; public class GFG{ // Function to return the // total different combination // possible static int total_count( string s, int n) { int ans = 1; int [] dp = new int [n]; for ( int i = 0; i < n; ++i) { dp[i] = 0; } // Base cases if (s[0] == '1' ) dp[0] = 1; if (s[1] == '1' && s[1] == s[0]) { dp[1] = 2; } else if (s[1] == '1' ) { dp[1] = 1; } // Iterating through every index // and storing the total // combination of string due to // all the adjacent 1's. for ( int i = 2; i < n; i++) { if (s[i] == '1' ) { if (s[i] == s[i - 1]) { if (s[i - 1] == s[i - 2]) { dp[i] = dp[i - 1] + dp[i - 2]; } else { dp[i] = 2; } } else { dp[i] = 1; } } } // Total combinations possible // by multiplying all the individual // combinations. for ( int i = 1; i < n; i++) { if (dp[i - 1] > dp[i]) { ans = ans * dp[i - 1]; } } // Edge case if (dp[n - 1] != 0) { ans = ans * dp[n - 1]; } // Returning the final value return ans; } // Driver code static public void Main (){ string str = "11011" ; int N; N = str.Length; // Function call Console.Write(total_count(str, N)); } } // This code is contributed by hrithikgarg03188. |
Javascript
<script> // JavaScript code to implement above approach // Function to return the // total different combination // possible const total_count = (s, n) => { let ans = 1, dp = new Array(n).fill(0); // Base cases if (s[0] == '1' ) dp[0] = 1; if (s[1] == '1' && s[1] == s[0]) { dp[1] = 2; } else if (s[1] == '1' ) { dp[1] = 1; } // Iterating through every index // and storing the total // combination of string due to // all the adjacent 1's. for (let i = 2; i < n; i++) { if (s[i] == '1') { if (s[i] == s[i - 1]) { if (s[i - 1] == s[i - 2]) { dp[i] = dp[i - 1] + dp[i - 2]; } else { dp[i] = 2; } } else { dp[i] = 1; } } } // Total combinations possible // by multiplying all the individual // combinations. for (let i = 1; i < n; i++) { if (dp[i - 1] > dp[i]) { ans = ans * dp[i - 1]; } } // Edge case if (dp[n - 1] != 0) { ans = ans * dp[n - 1]; } // Returning the final value return ans; } // Driver code let str = "11011" ; let N = str.length; // Function call document.write(total_count(str, N)); // This code is contributed by rakeshsahni </script> |
4
Time complexity: O(N)
Auxiliary Space: O(N)
Efficient approach: Using variables to optimize space complexity
The approach is same but to optimize space, we can replace the array dp with three variables to store the values for the last three positions. Since we only need the values of dp[i], dp[i-1], and dp[i-2] to calculate dp[i+1], we can use three variables instead of an entire array. This reduces the space complexity from O(n) to O(1).
Implementations Steps :
- Initialize variables ans, dp_0, dp_1, and dp_2 to 1, 0, 0, and 0 respectively.
- Check the base cases where the first character of the string is 1 and set dp_0 to 1. If the second character is also 1 and is the same as the first character, set dp_1 to 2. If the second character is 1 and is different from the first character, set dp_1 to 1.
- Iterate through the string starting from the third character. For each character, check if it is 1 or 0. If it is 1, update dp_0, dp_1, and dp_2 based on the presence of adjacent 1’s.
- Multiply ans with dp_1 or dp_2, whichever is larger. If dp_0 is not 0, multiply ans with dp_0.
- Return the final value of ans.
Implementation:
C++
// C++ program for above approach #include <bits/stdc++.h> using namespace std; // Function to return the // total different combination // possible int total_count(string s, int n) { int ans = 1, dp_0 = 0, dp_1 = 0, dp_2 = 0; // Base cases if (s[0] == '1' ) dp_0 = 1; if (s[1] == '1' && s[1] == s[0]) { dp_1 = 2; } else if (s[1] == '1' ) { dp_1 = 1; } // Iterating through every index // and storing the total // combination of string due to // all the adjacent 1's. for ( int i = 2; i < n; i++) { if (s[i] == '1' ) { if (s[i] == s[i - 1]) { if (s[i - 1] == s[i - 2]) { int temp = dp_2; dp_2 = dp_1 + dp_0; dp_0 = dp_1; dp_1 = temp; } else { dp_2 = dp_1; dp_1 = 2; dp_0 = dp_1; } } else { dp_2 = dp_1; dp_1 = 1; dp_0 = dp_1; } } else { dp_2 = dp_1; dp_1 = 0; dp_0 = dp_1; } } // Total combinations possible // by multiplying all the individual // combinations. if (dp_1 > dp_2) { ans = ans * dp_1; } else { ans = ans * dp_2; } // Edge case if (dp_0 != 0) { ans = ans * dp_0; } // Returning the final value return ans; } // Driver code int main() { string str = "11011" ; int N; N = str.size(); // Function call cout << total_count(str, N); return 0; } // this code is contributed by bhardwajji |
Java
public class Main { // Function to return the total different combination possible static int total_count(String s, int n) { int ans = 1 , dp_0 = 0 , dp_1 = 0 , dp_2 = 0 ; // Base cases if (s.charAt( 0 ) == '1' ) dp_0 = 1 ; if (s.charAt( 1 ) == '1' && s.charAt( 1 ) == s.charAt( 0 )) { dp_1 = 2 ; } else if (s.charAt( 1 ) == '1' ) { dp_1 = 1 ; } // Iterating through every index and storing the total combination // of string due to all the adjacent 1's. for ( int i = 2 ; i < n; i++) { if (s.charAt(i) == '1' ) { if (s.charAt(i) == s.charAt(i - 1 )) { if (s.charAt(i - 1 ) == s.charAt(i - 2 )) { int temp = dp_2; dp_2 = dp_1 + dp_0; dp_0 = dp_1; dp_1 = temp; } else { dp_2 = dp_1; dp_1 = 2 ; dp_0 = dp_1; } } else { dp_2 = dp_1; dp_1 = 1 ; dp_0 = dp_1; } } else { dp_2 = dp_1; dp_1 = 0 ; dp_0 = dp_1; } } // Total combinations possible by multiplying all the individual combinations. if (dp_1 > dp_2) { ans = ans * dp_1; } else { ans = ans * dp_2; } // Edge case if (dp_0 != 0 ) { ans = ans * dp_0; } // Returning the final value return ans; } // driver code to test above functions public static void main(String[] args) { String str = "11011" ; int N; N = str.length(); // Function call System.out.println(total_count(str, N)); } } |
Python3
def total_count(s: str , n: int ) - > int : ans, dp_0, dp_1, dp_2 = 1 , 0 , 0 , 0 # Base cases if s[ 0 ] = = '1' : dp_0 = 1 if s[ 1 ] = = '1' and s[ 1 ] = = s[ 0 ]: dp_1 = 2 elif s[ 1 ] = = '1' : dp_1 = 1 # Iterating through every index # and storing the total combination # of string due to all the adjacent 1's. for i in range ( 2 , n): if s[i] = = '1' : if s[i] = = s[i - 1 ]: if s[i - 1 ] = = s[i - 2 ]: temp = dp_2 dp_2 = dp_1 + dp_0 dp_0 = dp_1 dp_1 = temp else : dp_2 = dp_1 dp_1 = 2 dp_0 = dp_1 else : dp_2 = dp_1 dp_1 = 1 dp_0 = dp_1 else : dp_2 = dp_1 dp_1 = 0 dp_0 = dp_1 # Total combinations possible # by multiplying all the individual # combinations. if dp_1 > dp_2: ans = ans * dp_1 else : ans = ans * dp_2 # Edge case if dp_0 ! = 0 : ans = ans * dp_0 # Returning the final value return ans # Driver code if __name__ = = '__main__' : str = "11011" N = len ( str ) # Function call print (total_count( str , N)) |
C#
using System; public class MainClass { // Function to return the total different combination possible static int total_count( string s, int n) { int ans = 1, dp_0 = 0, dp_1 = 0, dp_2 = 0; // Base cases if (s[0] == '1' ) dp_0 = 1; if (s[1] == '1' && s[1] == s[0]) { dp_1 = 2; } else if (s[1] == '1' ) { dp_1 = 1; } // Iterating through every index and storing the total combination // of string due to all the adjacent 1's. for ( int i = 2; i < n; i++) { if (s[i] == '1' ) { if (s[i] == s[i - 1]) { if (s[i - 1] == s[i - 2]) { int temp = dp_2; dp_2 = dp_1 + dp_0; dp_0 = dp_1; dp_1 = temp; } else { dp_2 = dp_1; dp_1 = 2; dp_0 = dp_1; } } else { dp_2 = dp_1; dp_1 = 1; dp_0 = dp_1; } } else { dp_2 = dp_1; dp_1 = 0; dp_0 = dp_1; } } // Total combinations possible by multiplying all the // individual combinations. if (dp_1 > dp_2) { ans = ans * dp_1; } else { ans = ans * dp_2; } // Edge case if (dp_0 != 0) { ans = ans * dp_0; } // Returning the final value return ans; } // driver code to test above functions public static void Main( string [] args) { string str = "11011" ; int N; N = str.Length; // Function call Console.WriteLine(total_count(str, N)); } } |
Javascript
function total_count(s, n) { let ans = 1, dp_0 = 0, dp_1 = 0, dp_2 = 0; // Base cases if (s[0] == '1' ) { dp_0 = 1; } if (s[1] == '1' && s[1] == s[0]) { dp_1 = 2; } else if (s[1] == '1' ) { dp_1 = 1; } // Iterating through every index // and storing the total combination // of string due to all the adjacent 1's. for (let i = 2; i < n; i++) { if (s[i] == '1') { if (s[i] == s[i - 1]) { if (s[i - 1] == s[i - 2]) { let temp = dp_2; dp_2 = dp_1 + dp_0; dp_0 = dp_1; dp_1 = temp; } else { dp_2 = dp_1; dp_1 = 2; dp_0 = dp_1; } } else { dp_2 = dp_1; dp_1 = 1; dp_0 = dp_1; } } else { dp_2 = dp_1; dp_1 = 0; dp_0 = dp_1; } } // Total combinations possible // by multiplying all the individual // combinations. if (dp_1 > dp_2) { ans *= dp_1; } else { ans *= dp_2; } // Edge case if (dp_0 != 0) { ans *= dp_0; } // Returning the final value return ans; } // Driver code let str = "11011" ; let N = str.length; // Function call console.log(total_count(str, N)); |
Output:
4
Time complexity: O(N)
Auxiliary Space: O(1)
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!