Given a binary string of size N, the task is to count the number of alternating substrings that are present in the string S.
Examples:
Input: S = “0010”
Output: 7
Explanation:
All the substring of the string S are: {“0”, “00”, “001”, “0010”, “0”, “01”, “010”, “1”, “10”, “0”}
Strings that are alternating: {“0”, “0”, “01”, “010”, “1”, “10”, “0”}.
Hence, the answer is 7.Input: S = “010”
Output: 6
Naive Approach: The simplest approach to solve this problem is to first, find all the substrings of the string S, then check for every string if it is alternating or not.
Time Complexity: O(N3)
Auxiliary Space: O(N2)
Efficient Approach: This problem has Overlapping Subproblems property and Optimal Substructure property. So this problem can be solved using Dynamic Programming. Follow the steps below to solve this problem:
- Declare a dp array, where dp[i][j] stores the number of alternating strings that start with char i and are in the range [j, N-1].
- Iterate in the range [N-1, 0] using the variable i and perform the following steps:
- If i is equal to N-1, then if current character is ‘1’, then assign 1 to dp[1][i], otherwise assign 1 to dp[0][i].
- Else, if current character is ‘0’, then update dp[0][i] to 1+dp[1][i+1], otherwise, update dp[1][i] to 1+dp[0][i+1].
- Initialize a variable say ans as 0 to store the number of substrings that are alternating.
- Iterate in the range [0, N-1] using the variable i and perform the following steps:
- Update ans as max of dp[0][i] and dp[1][i].
- Finally, print the value obtained in ans as the answer.
Below is the implementation of the above approach:
C++
// c++ program for the above approach #include <bits/stdc++.h> using namespace std; // Function to count number of alternating // substrings from a given binary string int countAlternatingSubstrings(string S, int N) { // Initialize dp array, where dp[i][j] stores // the number of alternating strings starts // with i and having j elements. vector<vector< int > > dp(2, vector< int >(N, 0)); // Traverse the string from the end for ( int i = N - 1; i >= 0; i--) { // If i is equal to N - 1 if (i == N - 1) { if (S[i] == '1' ) dp[1][i] = 1; else dp[0][i] = 1; } // Otherwise, else { // Increment count of // substrings starting at i // and has 0 in the beginning if (S[i] == '0' ) dp[0][i] = 1 + dp[1][i + 1]; // Increment count of // substrings starting at i // and has 1 in the beginning else dp[1][i] = 1 + dp[0][i + 1]; } } // Stores the result int ans = 0; // Iterate in the range [0, N-1] for ( int i = 0; i < N; i++) { // Update ans ans += max(dp[0][i], dp[1][i]); } // Return the ans return ans; } // Driver code int main() { // Given Input string S = "0010" ; int N = S.length(); // Function call cout << countAlternatingSubstrings(S, N); return 0; } |
Java
// Java program for the above approach import java.util.*; class GFG{ // Function to count number of alternating // substrings from a given binary string static int countAlternatingSubstrings(String S, int N) { // Initialize dp array, where dp[i][j] stores // the number of alternating strings starts // with i and having j elements. int [][] dp = new int [ 2 ][N]; for ( int i = 0 ; i < 2 ; i++) { for ( int j = 0 ; j < N; j++) { dp[i][j] = 0 ; } } // Traverse the string from the end for ( int i = N - 1 ; i >= 0 ; i--) { // If i is equal to N - 1 if (i == N - 1 ) { if (S.charAt(i) == '1' ) dp[ 1 ][i] = 1 ; else dp[ 0 ][i] = 1 ; } // Otherwise, else { // Increment count of // substrings starting at i // and has 0 in the beginning if (S.charAt(i) == '0' ) dp[ 0 ][i] = 1 + dp[ 1 ][i + 1 ]; // Increment count of // substrings starting at i // and has 1 in the beginning else dp[ 1 ][i] = 1 + dp[ 0 ][i + 1 ]; } } // Stores the result int ans = 0 ; // Iterate in the range [0, N-1] for ( int i = 0 ; i < N; i++) { // Update ans ans += Math.max(dp[ 0 ][i], dp[ 1 ][i]); } // Return the ans return ans; } // Driver Code public static void main(String[] args) { // Given Input String S = "0010" ; int N = S.length(); // Function call System.out.print(countAlternatingSubstrings(S, N)); } } // This code is contributed by sanjoy_62 |
Python3
# Python3 program for the above approach # Function to count number of alternating # substrings from a given binary string def countAlternatingSubstrings(S, N): # Initialize dp array, where dp[i][j] stores # the number of alternating strings starts # with i and having j elements. dp = [[ 0 for i in range (N)] for i in range ( 2 )] # Traverse the string from the end for i in range (N - 1 , - 1 , - 1 ): # If i is equal to N - 1 if (i = = N - 1 ): if (S[i] = = '1' ): dp[ 1 ][i] = 1 else : dp[ 0 ][i] = 1 # Otherwise, else : # Increment count of # substrings starting at i # and has 0 in the beginning if (S[i] = = '0' ): dp[ 0 ][i] = 1 + dp[ 1 ][i + 1 ] # Increment count of # substrings starting at i # and has 1 in the beginning else : dp[ 1 ][i] = 1 + dp[ 0 ][i + 1 ] # Stores the result ans = 0 # Iterate in the range [0, N-1] for i in range (N): # Update ans ans + = max (dp[ 0 ][i], dp[ 1 ][i]) # Return the ans return ans # Driver code if __name__ = = '__main__' : # Given Input S = "0010" N = len (S) # Function call print (countAlternatingSubstrings(S, N)) # This code is contributed by mohit kumar 29 |
C#
// C# program for the above approach using System; class GFG{ // Function to count number of alternating // substrings from a given binary string static int countAlternatingSubstrings( string S, int N) { // Initialize dp array, where dp[i][j] stores // the number of alternating strings starts // with i and having j elements. int [,] dp = new int [2, N]; for ( int i = 0; i < 2; i++) { for ( int j = 0; j < N; j++) { dp[i, j] = 0; } } // Traverse the string from the end for ( int i = N - 1; i >= 0; i--) { // If i is equal to N - 1 if (i == N - 1) { if (S[i] == '1' ) dp[1, i] = 1; else dp[0, i] = 1; } // Otherwise, else { // Increment count of // substrings starting at i // and has 0 in the beginning if (S[i] == '0' ) dp[0, i] = 1 + dp[1, i + 1]; // Increment count of // substrings starting at i // and has 1 in the beginning else dp[1, i] = 1 + dp[0, i + 1]; } } // Stores the result int ans = 0; // Iterate in the range [0, N-1] for ( int i = 0; i < N; i++) { // Update ans ans += Math.Max(dp[0, i], dp[1, i]); } // Return the ans return ans; } // Driver Code public static void Main() { // Given Input string S = "0010" ; int N = S.Length; // Function call Console.Write(countAlternatingSubstrings(S, N)); } } // This code is contributed by target_2. |
Javascript
<script> // Javascript program for the above approach // Function to count number of alternating // substrings from a given binary string function countAlternatingSubstrings(S, N) { // Initialize dp array, where dp[i][j] stores // the number of alternating strings starts // with i and having j elements. var dp = new Array(2); dp[0] = Array(N).fill(0); dp[1] = Array(N).fill(0); var i; // Traverse the string from the end for (i = N - 1; i >= 0; i--) { // If i is equal to N - 1 if (i == N - 1) { if (S[i] == '1' ) dp[1][i] = 1; else dp[0][i] = 1; } // Otherwise, else { // Increment count of // substrings starting at i // and has 0 in the beginning if (S[i] == '0' ) dp[0][i] = 1 + dp[1][i + 1]; // Increment count of // substrings starting at i // and has 1 in the beginning else dp[1][i] = 1 + dp[0][i + 1]; } } // Stores the result var ans = 0; // Iterate in the range [0, N-1] for (i = 0; i < N; i++) { // Update ans ans += Math.max(dp[0][i], dp[1][i]); } // Return the ans return ans; } // Driver code // Given Input var S = "0010" ; var N = S.length; // Function call document.write(countAlternatingSubstrings(S, N)); // This code is contributed by SURENDRA_GANGWAR </script> |
7
Time Complexity: O(N)
Auxiliary Space: O(N)
Efficient approach: Space optimization O(1)
In previous approach we the current value dp[i] is only depend upon the previous 2 values i.e. dp[0][i-1], dp[1][i-1] . So to optimize the space we can keep track of previous and current values by the help of variables prev0, prev1 and curr0 ,curr1 which will reduce the space complexity from O(N) to O(1).
Implementation Steps:
- Create 2 variables prev0 and prev1 to keep track of previous values of DP.
- Initialize base case prev0 = prev1 = 0.
- Create variables curr0 and curr1 to store current value.
- Iterate over subproblem using loop and update curr0 , curr1.
- After every iteration update prev0 and prev1 for further iterations.
- At last return ans containing maximum of curr0 and curr1.
C++
// C++ code for above approach #include <bits/stdc++.h> using namespace std; // Function to count the number of alternating substrings int countAlternatingSubstrings(string S, int N) { // Initialize the previous counts for 0s and 1s to 0 int prev0 = 0, prev1 = 0; // Initialize the current counts for 0s and 1s int curr0, curr1; // to store answer int ans = 0; // iterate over subproblems to get the current // value from previous computations for ( int i = N - 1; i >= 0; i--) { // If the current character is 0 if (S[i] == '0' ) { curr0 = 1 + prev1; curr1 = 0; } // If the current character is 1 else { curr1 = 1 + prev0; curr0 = 0; } // Add the maximum of the current counts // for 0s and 1s to the answer variable ans += max(curr0, curr1); // assigning values for // further iterations prev0 = curr0; prev1 = curr1; } // Return the answer return ans; } // Driver Code int main() { string S = "0010" ; int N = S.length(); // funcition call cout << countAlternatingSubstrings(S, N); return 0; } // --- by bhardwajji |
Java
// Java code for above approach import java.util.*; class Main { // Function to count the number of alternating substrings public static int countAlternatingSubstrings(String S, int N) { // Initialize the previous counts for 0s and 1s to 0 int prev0 = 0 , prev1 = 0 ; // Initialize the current counts for 0s and 1s int curr0, curr1; // to store answer int ans = 0 ; // iterate over subproblems to get the current // value from previous computations for ( int i = N - 1 ; i >= 0 ; i--) { // If the current character is 0 if (S.charAt(i) == '0' ) { curr0 = 1 + prev1; curr1 = 0 ; } // If the current character is 1 else { curr1 = 1 + prev0; curr0 = 0 ; } // Add the maximum of the current counts // for 0s and 1s to the answer variable ans += Math.max(curr0, curr1); // assigning values for // further iterations prev0 = curr0; prev1 = curr1; } // Return the answer return ans; } // Driver Code public static void main(String[] args) { String S = "0010" ; int N = S.length(); // function call System.out.println(countAlternatingSubstrings(S, N)); } } |
Python
def count_alternating_substrings_optimized(S): # Initialize variables to keep track of counts and the result prev0 = prev1 = curr0 = curr1 = ans = 0 # Iterate over the string in reverse for i in range ( len (S) - 1 , - 1 , - 1 ): # If the current character is '0' if S[i] = = '0' : # Update counts for '0' and '1' curr0, curr1 = 1 + prev1, 0 else : # Update counts for '1' and '0' curr1, curr0 = 1 + prev0, 0 # Add the maximum of the current counts to the result ans + = max (curr0, curr1) # Update previous counts for the next iteration prev0, prev1 = curr0, curr1 # Return the final result return ans # Driver Code if __name__ = = "__main__" : # Example input S = "0010" # Call the function and print the result print (count_alternating_substrings_optimized(S)) |
C#
using System; class MainClass { // Function to count the number of alternating substrings public static int CountAlternatingSubstrings( string S, int N) { // Initialize the previous counts for 0s and 1s to 0 int prev0 = 0, prev1 = 0; // Initialize the current counts for 0s and 1s int curr0, curr1; // to store answer int ans = 0; // iterate over subproblems to get the current // value from previous computations for ( int i = N - 1; i >= 0; i--) { // If the current character is '0' if (S[i] == '0' ) { curr0 = 1 + prev1; curr1 = 0; } // If the current character is '1' else { curr1 = 1 + prev0; curr0 = 0; } // Add the maximum of the current counts // for 0s and 1s to the answer variable ans += Math.Max(curr0, curr1); // assigning values for // further iterations prev0 = curr0; prev1 = curr1; } // Return the answer return ans; } // Driver Code public static void Main( string [] args) { string S = "0010" ; int N = S.Length; // function call Console.WriteLine(CountAlternatingSubstrings(S, N)); } } |
Javascript
// Function to count the number of alternating substrings function countAlternatingSubstrings(S) { // Initialize the previous counts for 0s and 1s to 0 let prev0 = 0; let prev1 = 0; // Initialize the current counts for 0s and 1s let curr0, curr1; // Initialize the answer variable let ans = 0; // Iterate over the characters in the string from right to left for (let i = S.length - 1; i >= 0; i--) { // If the current character is '0' if (S[i] === '0' ) { curr0 = 1 + prev1; curr1 = 0; } // If the current character is '1' else { curr1 = 1 + prev0; curr0 = 0; } // Add the maximum of the current counts for '0's and '1's to the answer ans += Math.max(curr0, curr1); // Assign values for further iterations prev0 = curr0; prev1 = curr1; } // Return the answer return ans; } // Driver Code const S = "0010" ; const result = countAlternatingSubstrings(S); console.log(result); // Output the result |
7
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!