Homogenous Substrings

Easy

0/40

Average time to solve is 15m

Contributed by

0 upvote

Asked in company

Problem statement

You are given a string 'STR'. Your task is to count the number of homogenous substrings of ‘STR’. A substring is said to be homogenous, if and only if all the characters in the substring are the same. Also, a substring is a contiguous sequence of characters of the given string.

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

Input Format :

The first line contains an integer ‘T’, which denotes the number of test cases to be run. Then the test cases are as follows.

The first and the only line of each test case contains the string 'STR'.

Output Format :

For each test case, print an integer denoting the count of homogenous substrings.

Print the output of each test case in a separate line.

Note :

You don’t need to print anything; It has already been taken care of. Just implement the given function.

Constraints :

1 <= T <= 100
1 <= |STR| <= 10000
String STR contains only lowercase letters

Where '|STR|' denotes the length of the string.

Time limit: 1 sec

Sample Input 1 :

2
bcbc
ccddd

Sample Output 1 :

4
9

Explanation Of Sample Input 1 :

In the first test case, 
The homogenous substrings in the given string are:
“b” appears 2 times, and “c” appears 2 times, so total 4 homogenous substrings. Hence, the answer is 4 in this case.

In the second test case, 
“c” appears 2 times, “cc” appears 1 times, “d” appears 3 times, “dd” appears 2 times and “ddd” appears 1 time, so total 9 homogenous substrings. Hence, the answer is 9 in this case.

Sample Input 2 :

2
aaaaa
baabaab

Sample Output 2 :

15
9

Hint 1

Hint 2

Can you think of checking each substring?

Approaches (2)

Approach 1

Approach 2

Brute Force

The basic approach is to create all possible substrings from the given string and then count the number of homogenous substrings from them.

Algorithm:

Let N be the length of the given string.
Initialise a variable “count” with initial value 0 to store the total count of homogenous substrings.
Now we will iterate through all the substrings of the given string using two loops.
The first loop points towards the starting point of the substring, i = 0 to N-1
- The second loop points towards the ending point of substring, j = i to N-1
  - Start another loop that will check for all characters of the substring created.
  - If all characters in the substring are the same, then we will increment “count” by 1.
Return the variable 'count'.

Time Complexity

O(N^3), where N is the size of the string.

Since there are O(N^2) substrings that can be created using the string and each substring takes O(N) time to iterate through, the overall Time Complexity is O(N^3).

Space Complexity

O(1).

Constant extra space is required. Hence, the overall Space Complexity is O(1).

(100% EXP penalty)

Homogenous Substrings

Console