Last Updated: 10 Sep, 2021
Split the String
Moderate
Asked in companies
You are given a string ‘S’ consisting of lower-case English alphabets, find the number of good splits.
Splitting a string ‘S’ into two non-empty strings ‘X’ and ‘Y’ is called good if the number of unique characters in strings ‘X’ and ‘Y’ is equal.
For Example :
If string S is equal to “abadaa”.
Then S can be split in the following ways:
X = “a” and Y = “badaa”, string X has 1 unique character and Y has 3 unique characters.
X = “ab” and Y = “adaa”, string X has 2 unique characters and Y has 2 unique characters.[GOOD SPLIT]
X = “aba” and Y = “daa”, string X has 2 unique characters and Y has 2 unique characters.[GOOD SPLIT]
X = “abad” and Y = “aa”, string X has 3 unique characters and Y has 1 unique character.
X = “abada” and Y = “a”, string X has 3 unique characters and Y has 1 unique character.
Therefore we will return value 2 as we are able to find 2 good splits.
Input Format :
The first line contains a single integer ‘T’ denoting the number of test cases, then each test case follows:
The first line of each test case contains a string ‘S’ denoting the input string.
Output Format :
For each test case, print a single integer denoting the number of good splits.
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.
Constraints :
1 <= T <= 10
1 <= S.length <= 200
S contains only lower-case English alphabets
Time limit: 1 sec
Approaches
We can simply consider all the splits which lead to splitting the original string into two non-empty strings, for each of the strings we can calculate distinct characters in it with the help of a frequency array of size equal to 26 as there are 26 lower-case English alphabets.
We can finally return the number of good splits calculated.
The steps are as follows :
- Initialize “ans” equal to 0 to store the number of good splits.
- Run a for loop for variable “i” from 0 to S.length-2. Substring from 0…i will denote the string ‘X’ and substring (i+1)....(S.length-1) will denote the string ‘Y’.
- Calculate the number of distinct characters in strings ‘X’ and ‘Y’ using a frequency array “freq”.
- If the number of distinct characters in ‘X’ and ‘Y’ is equal then increment the value of “ans”.
- Finally, return the value stored in “ans”.
We can simply consider all the splits which lead to splitting the original string into two non-empty strings, we can precompute the number of distinct characters for the prefix substring from 0 to ‘i’ and also precompute the distinct characters in suffix substring from (i+1) to (S.length-1). If the number of distinct characters is equal then we can simply conclude that this split will be good.
We can finally return the number of good splits calculated.
The steps are as follows :
- Initialize “ans” equal to 0 to store the number of good splits.
- Initialize the “prefix” array to store the number of distinct characters in the substring from 0 to ‘i’ in ‘prefix[i]’.
- Initialize the “suffix” array to store the number of distinct characters in the substring from ‘i’ to ‘S.length-1’ in ‘suffix[i]’.
- Run a for loop for variable “i” from 0 to S.length-2. If prefix[i] is equal to suffix[i+1], then increment the value of “ans”.
- Finally, return the value stored in “ans”.
Similar problems