Last Updated: 12 Sep, 2021
Christmas At The Office
Moderate
Asked in company
Every year, on the day of Christmas, Everyone at The Dunder Mifflin paper company exchanges gifts. Jim always gives Pam the best Christmas gifts. But this time, Pam decided to give Jim a string having at most two different characters. Pam has a ternary string ‘s’. She wants to know how many total numbers of contiguous strings she can make from ‘s’ to gift Jim.
A ternary string is a string that does not have more than three different characters.
For Example :
Let s = “abbc”
Now In this example, Pam can make the following substrings:
a, b, b, c, ab, bb, bc, abb, bbc.
There are a total of 9 strings that she can gift Jim. Hence the answer is 9.
Input Format :
The first line contains a single integer ‘T’ denoting the number of test cases to be run. Then the test cases follow.
The first line of each test case contains a string ‘s’ denoting the ternary string.
Output Format :
For each test case, print a single integer “answer”, denoting the total number of strings she can make from the given string satisfying the given conditions.
Output for each test case will be printed in a separate line.
Note :
You are not required to print anything; it has already been taken care of. Just implement the function and return the answer.
Constraints :
1 <= T <= 100
1 <= |S| <= 10^4, where |S| denotes the length of string S.
Time limit: 1 sec
Approaches
In this approach, iterate through all the substrings from 0 to n-1 and count all the strings that satisfy the given conditions.
The steps are as follows:
- Take an integer “answer” in which we will store the final answer.
- Iterate through the string s from 0 to n-1(say iterator be i):
- Iterate through i to n-1(say iterator be j):
- Count the total number of distinct characters in the substring s[i…j], and if the count is less than three, increment “answer”.
- Iterate through i to n-1(say iterator be j):
- Return “answer”.
In this approach, we will take two pointers, ‘i’, ‘j’, denoting the starting and ending points of a substring and check if that substring contains more than two different characters.
The steps are as follows:
- Take three integers, “greater”, ‘j’, and ‘i’, in which we will store the count of strings greater than 2, the starting position of the substring, and the ending position, respectively.
- Take an array “counter” to store the number of characters present in the current substring.
- Take a while loop and increment ‘i’ till i<n:
- Increment “counter[s[i]]”.
- If counter[s[i]]==1, increment size.
- Check if “elementCount” is greater than 2, then start increasing the starting point till the elements in the substring equal 2.
- Update “greater” = “greater” + ‘j’.
- Increment ‘i’.
- Return n * (n - 1)/2 - “greater”.