Christmas At The Office

Moderate
0/80
profile
Contributed by
12 upvotes
Asked in company
Adobe

Problem statement

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.
Detailed explanation ( Input/output format, Notes, Images )
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
Sample Input 1 :
2
abc
aabc
Sample Output 1 :
5
8
Explanation For Sample Output 1 :
For the first test case, she can make strings: a, b, c, ab, bc.
Hence the answer is 5.

For the second test case, she can make the following strings - a, a, b, c, aa, ab, bc, and aab. 
Hence the final answer is 8.
Sample Input 2 :
2
jim
beet
Sample Output 2 :
5
9
Hint

Iterate through all possible substrings and count all the strings satisfying the given conditions.

Approaches (2)
Naive approach

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”.
  • Return “answer”.
Time Complexity

O( |S| ^ 2 ), where |S| denotes the length of string S

 

Since we are iterating through the whole string ‘s’ in a nested for loop.

Hence, the total time complexity of this approach will be O( |s| ^ 2 ).

Space Complexity

O( 1 ).

 

We are not using any extra space.

Hence the space complexity will be O( 1 ).

Code Solution
(100% EXP penalty)
Christmas At The Office
Full screen
Console