Number of Substrings Containing All Three Characters

Last Updated on March 31, 2022 by Ria Pathak

Concepts Used

Strings, Sliding Window Algorithm using two pointers

Difficulty Level

Medium

Problem Statement (Simplified):

Print the number of substrings containing all three characters i.e. a,b,c at least once in a given string.

See original problem statement here

Test Case

Input:
1
acbaa

Output:
5

Explanation:
The substrings containing at least one occurrence of the characters a, b and c are acb, acba, acbaa, cba and cbaa. 

Solving Approach :

Bruteforce Approach:

1) Find all possible substrings of a string.
2) Find the number of the appearance of a, b and c in every substring.
3) If all three found, increase the counter by 1.
4) Repeat till all substrings are checked.
5) In the current approach, we can find all substrings in O(N²) time and O(N) time to check the presence of characters a,b,c in every substring. So total time complexity for this approach is O(N⁴). We can see size constraint for the length of the string goes up to 10⁴ and we can’t go with this approach. We follow a more efficient approach to solve this problem.

Efficient Approach :

1) You can see in the above approach, we were able to find the answer but it was taking longer times. So we use the Sliding Window Algorithm with use of two pointers start and end .
2) A window contains characters from the index start to end-1.
3) In each window, we calculate a number of appearances of each character. If all the character is present in sliding window then all the substrings, substring(start, end), substring(start, end + 1), …, substring(start, n) are valid substrings., and we increase the counter by N - end + 1 where N is the length of String.
4) Finally algorithm finishes when end reaches to the end of the string and the final counter is printed.

Example

• Lets take string in test cases for example i.e. acbaa.
• We check window usibg above approachb for this string.
  
• In above diagram, we can see we get eligible windows at two position :
  

  • At start = 0 and end = 3, so total number of substring will be N-end+1 i.e. 3. These substrings are acb, acba and acbaa.
  • At start = 1 and end = 4, so total number of substring will be N-end+1 i.e. 2. These substrings are cba and cbaa.

• So, our final answer is 5.

Solutions

 #include <stdio.h>

    int main()
    {
      int test;
      scanf("%d",&test);

      while(test--){

        char S[100000];
        scanf("%s", S);

        int start=0, end=0, count=0;

        if(strlen(S)<3)
          count = 0;
        else{
            while(end <= strlen(S)){

              int hash[26] = {0};
              for(int i=start; i<end; i++){
                  hash[ S[i] - 'a' ]++;
              }

              if(hash[0]>0 && hash[1]>0 && hash[2]>0){
                  count += strlen(S) - end + 1;
                  start++;
              }else{
                  end++;
              }


            }
        }

        printf("%d\n", count);

      }
    }

#include <bits/stdc++.h>
    using namespace std;

    int main()
    {
      int test;
      cin>>test;

      while(test--){

        char S[100000];
        cin>>S;

        int start=0, end=0, count=0;

        if(strlen(S)<3)
          count = 0;
        else{
            while(end <= strlen(S)){

              int hash[26] = {0};
              for(int i=start; i<end; i++){
                  hash[ S[i] - 'a' ]++;
              }

              if(hash[0]>0 && hash[1]>0 && hash[2]>0){
                  count += strlen(S) - end + 1;
                  start++;
              }else{
                  end++;
              }


            }
        }

        cout<<count<<endl;

      }
      return 0;
    }

import java.util.*;
    import java.io.*;

    public class Main {
      public static void main(String args[]) throws IOException {
        Scanner sc= new Scanner(System.in);
        int test_cases;
        test_cases = sc.nextInt();

        while(test_cases != 0){

            String S = sc.next();
            int start=0, end=0, count=0;

            if(S.length()<3)
              count = 0;
            else{
                while(end <= S.length()){

                  int hash[] = new int[26];
                  hash[0] = 0;
                  hash[1] = 0;
                  hash[2] = 0;
                  for(int i=start; i<end; i++){
                      hash[ S.charAt(i) - 'a' ]++;
                  }

                  if(hash[0]>0 && hash[1]>0 && hash[2]>0){
                      count += S.length() - end + 1;
                      start++;
                  }
                  else{
                      end++;
                  }


                }
            }

            System.out.println(count);
            test_cases--;

        }
      }
    }

for _ in range(int(input())):
	
	s = input()
	start, end, count = 0, 0, 0

	if len(s) < 3:
		count = 0

	else:
		while end <= len(s):

			hash = [0 for i in range(26)]

			for i in range(start, end):

				hash[ord(s[i]) - ord("a")] += 1

			if hash[0] > 0 and hash[1] > 0 and hash[2] > 0:
				count += len(s) - end + 1
				start += 1

			else:
				end += 1
	print(count)

[forminator_quiz id="1590"]

This article tried to discuss the concept of Strings. Hope this blog helps you understand and solve the problem. To practice more problems on Strings you can check out MYCODE | Competitive Programming.