Count Substring With abc

Easy

0/40

Contributed by

23 upvotes

Asked in company

Problem statement

Count the number of substrings which contains at least one occurrence of all these characters: a, b, and c.

Note:

The count of substrings will always fit in a 32-bit integer.

Example:

For 'n' = 5, 's’ = “abbac”.
Answer is 3.
These are the only 3 valid substrings { “abbac”, ”bbac”, ”bac” } satisfying all the constraints.

Detailed explanation ( Input/output format, Notes, Images )

Input format:

The first line contains an integer 'n', representing the size of the input string ‘s’.

The second line contains a string 's' representing the input string.

Output Format:

Return the value as explained in the statement.

Note:

You don’t need to print anything, it has already been taken care of. Just complete the given function.

Sample Input 1:

4
baac

Sample Output 1:

Explanation of sample output 1:

‘n’ = 4,'s’ = “baac”.
Answer is 1. The only possible substring is “baac”.

Sample Input 2:

8
bababcc

Sample Output 2:

Constraints:

1 <= n <= 10^5
's' only contains a,b,c.
Time Limit: 1 sec

Hint 1

Hint 2

Check all possible substrings.

Approaches (2)

Approach 1

Approach 2

Brute force

We will consider all possible substrings of the given string ‘s’. For each substring, we will check if it contains at least one occurrence of all the characters a, b, and c. If a substring satisfies this condition, we can count it towards our final answer.

Algorithm:

Initialise variable ‘ans’ = 0
Initialise variable ‘n’ = s.length
for ‘i’ from ‘0’ to ‘n’-1
- Initialise variable ‘countA’ = 0, ‘countB’ = 0, ‘countC’=0
- for ‘j’ from ‘i’ to ‘n’ -1
  - If s[j] == ‘a’
    - ‘countA’++
  - If s[j] == ‘b’
    - ‘countB’++
  - If s[j] == ‘c’
    - ‘countC’++
  - If ‘countA’ >= 1 AND ‘countB’ >= 1 AND ‘countC’ >= 1
    - ‘ans’++
return ‘ans’

Time Complexity

O(n^2), where ‘n’ is the size of a string ’s'.

We are iterating via ‘i’ from ‘0’ to ‘n’-1, and for each ‘i’, we are iterating via ‘j’ from ‘i’ to ‘n’-1. Hence the overall time complexity of this solution is O(n^2).

Space Complexity

O(1).

We are not utilising any extra space here, hence the O(1) space complexity.

(100% EXP penalty)

Count Substring With abc

Console