Given a binary string T (consisting of 0 and 1) of length exactly 26, which indicates a frequency constraints of first 26 lowercase alphabets. T[i] = ‘1’ indicates i’th alphabet can occur at most once and T[i] = ‘0’ indicates i’th alphabet can occur any number of times. String T is 1 indexed and Alphabets are numbered from 1 to 26. 1st alphabet is ‘a’, 2nd alphabet is ‘b’ …….. and 26th alphabet is ‘z’.
Any string is beautiful if all the characters present in it follows the constraint T.
Given a string S consisting of N lowercase alphabets, count the number of beautiful substrings. Two substrings will be considered different for the answer if either the starting or ending index is different.
A substring is a contiguous sequence of characters within a string.
The first line of input contains a string S.
Next line contains the string T.
1 <= Length of S <= 5 * 10^5
Length of T = 26
Output the number of beautiful substrings in the given string.
Input | Output |
---|---|
abca 10101111111111111111111111 | 9 |
In this example, the constraint T indicates, only b and d can occur any number of times & all other character can occur at most once. There are 9 such substrings in the string which follows this constraint. |