{"id":1548,"date":"2020-06-11T09:41:04","date_gmt":"2020-06-11T09:41:04","guid":{"rendered":"https:\/\/blog.prepbytes.com\/?p=1548"},"modified":"2022-03-31T12:32:31","modified_gmt":"2022-03-31T12:32:31","slug":"number-of-substrings-containing-all-three-characters","status":"publish","type":"post","link":"https:\/\/prepbytes.com\/blog\/number-of-substrings-containing-all-three-characters\/","title":{"rendered":"Number of Substrings Containing All Three Characters"},"content":{"rendered":"

\"\"<\/p>\n

Concepts Used<\/h3>\n
\n

Strings, Sliding Window Algorithm using two pointers<\/p>\n<\/blockquote>\n

Difficulty Level<\/h3>\n
\n

Medium<\/p>\n<\/blockquote>\n

Problem Statement (Simplified):<\/h3>\n
\n

Print the number of substrings containing all three characters i.e. a,b,c at least once in a given string.<\/p>\n<\/blockquote>\n

<\/strong><\/u><\/a><\/p>\n

Test Case<\/h3>\n
Input:\n1\nacbaa\n\nOutput:\n5\n\nExplanation:\nThe substrings containing at least one occurrence of the characters a, b and c are acb, acba, acbaa, cba and cbaa. <\/code><\/pre>\n
Solving Approach :<\/h3>\n
Bruteforce Approach:<\/h4>\n
\n
1) Find all possible substrings of a string.
\n2) Find the number of the appearance of a, b and c in every substring.
\n3) If all three found, increase the counter by 1.
\n4) Repeat till all substrings are checked.
\n5) In the current approach, we can find all substrings in O(N2<\/sup>) time and O(N)<\/code> time to check the presence of characters a,b,c<\/code> in every substring. So total time complexity for this approach is O(N4<\/sup>). We can see size constraint for the length of the string goes up to 104<\/sup> and we can’t go with this approach. We follow a more efficient approach to solve this problem. <\/p>\n<\/blockquote>\n
Efficient Approach :<\/h4>\n
\n
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<\/code> and end <\/code>.
\n2) A window contains characters from the index start<\/code> to end-1<\/code>.
\n3) 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)<\/code>, substring(start, end + 1)<\/code>, \u2026, substring(start, n)<\/code> are valid substrings., and we increase the counter by N - end + 1<\/code> where N is the length of String.
\n4) Finally algorithm finishes when end reaches to the end of the string and the final counter is printed.<\/p>\n<\/blockquote>\n
Example<\/h4>\n
\n
    \n
  • Lets take string in test cases for example i.e. acbaa<\/code>.<\/li>\n
  • We check window usibg above approachb for this string.
    \n\"\"<\/li>\n
  • In above diagram, we can see we get eligible windows at two position :
    \n
    \n
      \n
    • At start = 0<\/code> and end = 3<\/code>, so total number of substring will be N-end+1<\/code> i.e. 3. These substrings are acb<\/code>, acba<\/code> and acbaa<\/code>.<\/li>\n
    • At start = 1<\/code> and end = 4<\/code>, so total number of substring will be N-end+1<\/code> i.e. 2. These substrings are cba<\/code> and cbaa<\/code>.<\/li>\n<\/ul>\n<\/blockquote>\n<\/li>\n
    • So, our final answer is 5.<\/li>\n<\/ul>\n<\/blockquote>\n
      Solutions<\/h3>\n
      \t\t\t\t\t\t