# Count subsequences 01 in string generated by concatenation of given numeric string K times

Given a string **S** and a positive integer **K**, the task is to find the number of subsequences **“01”** in the string generated by concatenation of the given numeric string **S** **K times**.

**Examples:**

Attention reader! Don’t stop learning now. Get hold of all the important DSA concepts with the **DSA Self Paced Course** at a student-friendly price and become industry ready. To complete your preparation from learning a language to DS Algo and many more, please refer **Complete Interview Preparation Course****.**

In case you wish to attend **live classes **with experts, please refer **DSA Live Classes for Working Professionals **and **Competitive Programming Live for Students**.

Input:S = “0171”, K = 2Output:6Explanation:

The string formed by concatenation of S, K number of times is “01710171”. There are total 6 possible subsequences which are marked as bold = {“01710171″, “01710171″, “01710171″, “01710171“, “01710171″, “01710171“}.

Input:S = “230013110087”, K = 2Output:24

**Naive Approach:** The simplest approach to solve the given problem is to generate the resultant string by concatenating **S**, **K** number of times and then find all possible pairs (i, j) from the string such that **(i < j)** and **S[i] = 0** and **S[j] = 1**.

**Time Complexity:** O((N*K)^{2})**Auxiliary Space:** O(N*K)

**Efficient Approach:** The task can also be optimized by observing the following 2 Cases:

**Case 1:**Substring**“01”**strictly inside each occurrence of**S**in**P**. Let suppose**C**be the count of occurrences of**“01”**in**S**, then in**P**it would be**C*K**.**Case 2:**When ‘**0**‘ lies**inside**at i^{th}occurrence of**S**and ‘**1**‘ lies inside some j^{th}occurrence to form a subsequence “**01**” such that i < j, then finding the number of occurrences of “**01**” will be the same as choosing the two strings or occurrence of strings in**P**given by**((K)*(K – 1))/2**. Let that value be S_{i }and S_{j}and multiplying it by the number of occurrences of ‘0’ in S_{i}(denoted by**cnt0**) and a number of occurrences of ‘1’ in S_{j}(denoted by**cnt1**) gives the number of subsequences of “01”.

Below is the implementation of the above approach:

## C++

`// C++ program for the above approach` `#include <bits/stdc++.h>` `using` `namespace` `std;` `// Function to calculate the number of` `// subsequences of "01"` `int` `countSubsequence(string S, ` `int` `N,` ` ` `int` `K)` `{` ` ` `// Store count of 0's and 1's` ` ` `int` `C = 0, C1 = 0, C0 = 0;` ` ` `for` `(` `int` `i = 0; i < N; i++) {` ` ` `if` `(S[i] == ` `'1'` `)` ` ` `C1++;` ` ` `else` `if` `(S[i] == ` `'0'` `)` ` ` `C0++;` ` ` `}` ` ` `// Count of subsequences without` ` ` `// concatenation` ` ` `int` `B1 = 0;` ` ` `for` `(` `int` `i = 0; i < N; i++) {` ` ` `if` `(S[i] == ` `'1'` `)` ` ` `B1++;` ` ` `else` `if` `(S[i] == ` `'0'` `)` ` ` `C = C + (C1 - B1);` ` ` `}` ` ` `// Case 1` ` ` `int` `ans = C * K;` ` ` `// Case 2` ` ` `ans += (C1 * C0 * (((K) * (K - 1)) / 2));` ` ` `// Return the total count` ` ` `return` `ans;` `}` `// Driver Code` `int` `main()` `{` ` ` `string S = ` `"230013110087"` `;` ` ` `int` `K = 2;` ` ` `int` `N = S.length();` ` ` `cout << countSubsequence(S, N, K);` ` ` `return` `0;` `}` |

## Java

`// Java program for the above approach` `import` `java.io.*;` `class` `GFG {` ` ` `// Function to calculate the number of` ` ` `// subsequences of "01"` ` ` `static` `int` `countSubsequence(String S, ` `int` `N, ` `int` `K)` ` ` `{` ` ` `// Store count of 0's and 1's` ` ` `int` `C = ` `0` `, C1 = ` `0` `, C0 = ` `0` `;` ` ` `for` `(` `int` `i = ` `0` `; i < N; i++) {` ` ` `if` `(S.charAt(i) == ` `'1'` `)` ` ` `C1++;` ` ` `else` `if` `(S.charAt(i) == ` `'0'` `)` ` ` `C0++;` ` ` `}` ` ` `// Count of subsequences without` ` ` `// concatenation` ` ` `int` `B1 = ` `0` `;` ` ` `for` `(` `int` `i = ` `0` `; i < N; i++) {` ` ` `if` `(S.charAt(i) == ` `'1'` `)` ` ` `B1++;` ` ` `else` `if` `(S.charAt(i) == ` `'0'` `)` ` ` `C = C + (C1 - B1);` ` ` `}` ` ` `// Case 1` ` ` `int` `ans = C * K;` ` ` `// Case 2` ` ` `ans += (C1 * C0 * (((K) * (K - ` `1` `)) / ` `2` `));` ` ` `// Return the total count` ` ` `return` `ans;` ` ` `}` ` ` `// Driver Code` ` ` `public` `static` `void` `main(String[] args)` ` ` `{` ` ` `String S = ` `"230013110087"` `;` ` ` `int` `K = ` `2` `;` ` ` `int` `N = S.length();` ` ` `System.out.println(countSubsequence(S, N, K));` ` ` `}` `}` `// This code is contributed by Potta Lokesh` |

## Python3

`# python program for the above approach` `# Function to calculate the number of` `# subsequences of "01"` `def` `countSubsequence(S, N, K):` ` ` `# Store count of 0's and 1's` ` ` `C ` `=` `0` ` ` `C1 ` `=` `0` ` ` `C0 ` `=` `0` ` ` `for` `i ` `in` `range` `(` `0` `, N):` ` ` `if` `(S[i] ` `=` `=` `'1'` `):` ` ` `C1 ` `+` `=` `1` ` ` `elif` `(S[i] ` `=` `=` `'0'` `):` ` ` `C0 ` `+` `=` `1` ` ` `# Count of subsequences without` ` ` `# concatenation` ` ` `B1 ` `=` `0` ` ` `for` `i ` `in` `range` `(` `0` `, N):` ` ` `if` `(S[i] ` `=` `=` `'1'` `):` ` ` `B1 ` `+` `=` `1` ` ` `elif` `(S[i] ` `=` `=` `'0'` `):` ` ` `C ` `=` `C ` `+` `(C1 ` `-` `B1)` ` ` `# Case 1` ` ` `ans ` `=` `C ` `*` `K` ` ` `# Case 2` ` ` `ans ` `+` `=` `(C1 ` `*` `C0 ` `*` `(((K) ` `*` `(K ` `-` `1` `)) ` `/` `/` `2` `))` ` ` `# Return the total count` ` ` `return` `ans` `# Driver Code` `if` `__name__ ` `=` `=` `"__main__"` `:` ` ` `S ` `=` `"230013110087"` ` ` `K ` `=` `2` ` ` `N ` `=` `len` `(S)` ` ` `print` `(countSubsequence(S, N, K))` ` ` `# This code is contributed by rakeshsahni` |

## C#

`// C# implementation for the above approach` `using` `System;` `class` `GFG` `{` ` ` `// Function to calculate the number of` ` ` `// subsequences of "01"` ` ` `static` `int` `countSubsequence(` `string` `S, ` `int` `N, ` `int` `K)` ` ` `{` ` ` ` ` `// Store count of 0's and 1's` ` ` `int` `C = 0, C1 = 0, C0 = 0;` ` ` `for` `(` `int` `i = 0; i < N; i++) {` ` ` `if` `(S[i] == ` `'1'` `)` ` ` `C1++;` ` ` `else` `if` `(S[i] == ` `'0'` `)` ` ` `C0++;` ` ` `}` ` ` `// Count of subsequences without` ` ` `// concatenation` ` ` `int` `B1 = 0;` ` ` `for` `(` `int` `i = 0; i < N; i++) {` ` ` `if` `(S[i] == ` `'1'` `)` ` ` `B1++;` ` ` `else` `if` `(S[i] == ` `'0'` `)` ` ` `C = C + (C1 - B1);` ` ` `}` ` ` `// Case 1` ` ` `int` `ans = C * K;` ` ` `// Case 2` ` ` `ans += (C1 * C0 * (((K) * (K - 1)) / 2));` ` ` `// Return the total count` ` ` `return` `ans;` ` ` `}` ` ` `// Driver Code` ` ` `public` `static` `void` `Main()` ` ` `{` ` ` `string` `S = ` `"230013110087"` `;` ` ` `int` `K = 2;` ` ` `int` `N = S.Length;` ` ` `Console.Write(countSubsequence(S, N, K));` ` ` `}` `}` `// This code is contributed by sanjoy_62.` |

## Javascript

`<script>` `// Javascript program for the above approach` `// Function to calculate the number of` `// subsequences of "01"` `function` `countSubsequence(S, N, K) {` ` ` `// Store count of 0's and 1's` ` ` `let C = 0,` ` ` `C1 = 0,` ` ` `C0 = 0;` ` ` `for` `(let i = 0; i < N; i++) {` ` ` `if` `(S[i] == ` `"1"` `) C1++;` ` ` `else` `if` `(S[i] == ` `"0"` `) C0++;` ` ` `}` ` ` `// Count of subsequences without` ` ` `// concatenation` ` ` `let B1 = 0;` ` ` `for` `(let i = 0; i < N; i++) {` ` ` `if` `(S[i] == ` `"1"` `) B1++;` ` ` `else` `if` `(S[i] == ` `"0"` `) C = C + (C1 - B1);` ` ` `}` ` ` `// Case 1` ` ` `let ans = C * K;` ` ` `// Case 2` ` ` `ans += C1 * C0 * ((K * (K - 1)) / 2);` ` ` `// Return the total count` ` ` `return` `ans;` `}` `// Driver Code` `let S = ` `"230013110087"` `;` `let K = 2;` `let N = S.length;` `document.write(countSubsequence(S, N, K));` `// This code is contributed by gfgking.` `</script>` |

**Output:**

24

**Time Complexity:** O(N)**Auxiliary Space:** O(1)