Last Updated: 9 Apr, 2021
Homogenous Substrings
Easy
Asked in company
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.
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
Approaches
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.
- The second loop points towards the ending point of substring, j = i to N-1
- Return the variable 'count'.
The basic idea behind this approach is to find the length of the same characters before the current character and add it to the total count of homogenous substrings. Let us understand this better with the help of an example:
Let “STR” = aabbb
Now we will start traversing,
=> “current” = a, continuousCharacterCount = 1, so adding into result, result = 1
=> next character = a, continuousCharacterCount = 2, adding into result, result = 3
=> next character = b, continuousCharacterCount = 1, adding into result, result = 4
=> next character = b, continuousCharacterCount = 2, adding into result, result = 6
=> next character = b, continuousCharacterCount = 3, adding into result, result = 9
Algorithm:
- Initialise two variables “result” = 0 and “continuousCharacterCount” = 0, “result” will store the total count of homogenous substrings, while “continuousCharacterCount” will store the count of same characters before the current character.
- Initialise a variable “current” that will store the current character which is being used in the approach.
- Iterate through the given string and compare “current” with character at the loop's position.
- If both are equal, increment “continuousCharacterCount”.
- Otherwise,
- Update “continuousCharacterCount” = 1, as it is the first occurrence of that character.
- And update the “current” character, as the current character changed and now we have to find the substrings of this character.
- After every traversal, we will add “continuousCharacterCount” to “result”.
- Return “result”.