Last Updated: 14 May, 2023

Count Substring With abc

Easy

Asked in company

Solve now

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.

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.

Solve now

Approaches

01 Approach

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’

Solve now

02 Approach

We will be maintaining three pointers each for characters ‘a’, ‘b’ and ‘c’ i.e ‘aIdx’, ‘bIdx’ and ‘cIdx’ initially initialised to -1 for maintaining the last index of their occurrence.
We will be iterating via ‘i’ from 0 to ‘n’-1. For each ‘i’ we will update the counters depending on the s[i].
Once we update the counters, we have to find the last index we essentially have to include to make a valid substring ending at ‘i’. All the substrings before that last index and ending at ‘i’ would be valid.
The last index is nothing but the minimum of all ‘aIdx’, ‘bIdx’ and ‘cIdx’. We will add all the valid substrings ending at ‘i’ to the final answer.

Algorithm:

initialise variable ‘ans’ = 0
initialise variable ‘n’ = s.length
Initialise variables ‘aIdx’ = -1, ‘bIdx’ = -1 and ‘cIdx’ = -1
for ‘i’ from ‘0’ to ‘n’-1
- If s[i] == ‘a’
  - ‘aIdx’ = i
- If s[i] == ‘b’
  - ‘bIdx’ = i
- If s[i] == ‘c’
  - ‘cIdx’ = i
- Initialise variable minIdx = min( aIdx, min( bIdx, cIdx ))
- ‘ans’ = ‘ans’ + (minIdx+1)
return ‘ans’

Solve now