Given string str of size N consisting of only 0, 1, and 2, the task is to find the number of substrings that consists of characters 0, 1, and 2 at least once.
Examples:
Input: str = “0122”
Output: 2
Explanation:
There exists 2 substrings such that the substrings has characters 0, 1, 2 at least once is “012” and “0122”. Therefore, the count of substrings is 2.Input: S = “00021”
Output: 3
Approach: The given problem can be solved using the Sliding Window Technique, the idea is to make the frequency array of the size 3 that contains the occurrence of 0, 1, and 2. Traverse the given string and update the freq array accordingly, if all 3 indexes in the array are greater than zero then count the minimum of them and increment it into variable count. Follow the steps below to solve the problem:
- Initialize an array freq[] of size 3 to store the frequency of all elements in the array.
- Initialize the variable count as 0 to store the answer and i as 0 to maintain the left pointer.
- Iterate over the range [0, N) using the variable j and perform the following tasks:
- Increase the frequency of the current character str[I] in the array freq[] by 1.
- Traverse in a while loop till freq[0], freq[1], and freq[2] are greater than 0, decrease the frequency of the character at i-th position by 1 and increase the value of i by 1.
- Add the value of i to the variable count.
- After performing the above steps, print the value of count as the answer.
Below is the implementation of the above approach.
C++
// C++ program for above approach#include <iostream>#include <string>using namespace std;// Function to count the number of// substrings consists of 0, 1, and 2int countSubstrings(string& str){ // Initialize frequency array // of size 3 int freq[3] = { 0 }; // Stores the resultant count int count = 0; int i = 0; // Traversing string str for (int j = 0; j < str.length(); j++) { // Update frequency array freq[str[j] - '0']++; // If all the characters are // present counting number of // substrings possible while (freq[0] > 0 && freq[1] > 0 && freq[2] > 0) { freq[str[i++] - '0']--; } // Update number of substrings count += i; } // Return the number of substrings return count;}// Driver Codeint main(){ string str = "00021"; int count = countSubstrings(str); cout << count; return 0;}// This code is contributed by Kdheeraj. |
Java
// Java program for the above approachimport java.util.*;class GFG { // Function to count the number of // substrings consists of 0, 1, and 2 public static int countSubstrings(String str) { // Initialize frequency array // of size 3 int[] freq = new int[3]; // Stores the resultant count int count = 0; int i = 0; // Traversing string str for (int j = 0; j < str.length(); j++) { // Update frequency array freq[str.charAt(j) - '0']++; // If all the characters are // present counting number of // substrings possible while (freq[0] > 0 && freq[1] > 0 && freq[2] > 0) { freq[str.charAt(i++) - '0']--; } // Update number of substrings count += i; } // Return the number of substrings return count; } // Driver Code public static void main(String[] args) { String str = "00021"; System.out.println( countSubstrings(str)); }} |
Python3
# Python program for above approach# Function to count the number of# substrings consists of 0, 1, and 2def countSubstrings(str): # Initialize frequency array # of size 3 freq = [ 0 ]*3 # Stores the resultant count count = 0 i = 0 # Traversing string str for j in range ( 0 ,len(str)): # Update frequency array freq[ord(str[j]) - ord('0')] += 1 # If all the characters are # present counting number of # substrings possible while (freq[0] > 0 and freq[1] > 0 and freq[2] > 0): i += 1 freq[ord(str[i]) - ord('0')] -= 1 # Update number of substrings count += i # Return the number of substrings return count# Driver Codestr = "00021"count = countSubstrings(str)print(count)# This code is contributed by shivanisinghss2110 |
C#
// C# program for the above approachusing System;class GFG { // Function to count the number of // substrings consists of 0, 1, and 2 public static int countSubstrings(string str) { // Initialize frequency array // of size 3 int[] freq = new int[3]; // Stores the resultant count int count = 0; int i = 0; // Traversing string str for (int j = 0; j < str.Length; j++) { // Update frequency array freq[str[j] - '0']++; // If all the characters are // present counting number of // substrings possible while (freq[0] > 0 && freq[1] > 0 && freq[2] > 0) { freq[str[i++] - '0']--; } // Update number of substrings count += i; } // Return the number of substrings return count; } // Driver Code public static void Main(String[] args) { string str = "00021"; Console.Write(countSubstrings(str)); }}// This code is contributed by shivanisinghss2110 |
Javascript
<script> // JavaScript Program to implement // the above approach // Function to count the number of // substrings consists of 0, 1, and 2 function countSubstrings(str) { // Initialize frequency array // of size 3 let freq = new Array(3).fill(0) // Stores the resultant count let count = 0; let i = 0; // Traversing string str for (let j = 0; j < str.length; j++) { // Update frequency array freq[str.charCodeAt(j) - '0'.charCodeAt(0)]++; // If all the characters are // present counting number of // substrings possible while (freq[0] > 0 && freq[1] > 0 && freq[2] > 0) { freq[str.charCodeAt(i++) - '0'.charCodeAt(0)]--; } // Update number of substrings count += i; } // Return the number of substrings return count; } // Driver Code let str = "00021"; let count = countSubstrings(str); document.write(count);// This code is contributed by Potta Lokesh </script> |
Output:
3
Time Complexity: O(N)
Auxiliary Space: O(1)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!