Split the String

Moderate
0/80
profile
Contributed by
8 upvotes
Asked in companies
WalmartAmazonLumen Technologies

Problem statement

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.
Detailed explanation ( Input/output format, Notes, Images )
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
Sample Input 1 :
2
abadaa
abcde
Sample Output 1 :
2
0
Explanation For Sample Input 1 :
For test case 1 : 
We will return 2, because only 2 good splits are possible as shown below:
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.

For test case 2 : 
We will return 0, because no good split is possible. All possible splits are shown:
X = “a” and Y = “bcde”, string X has 1 unique character and Y has 4 unique characters.
X = “ab” and Y = “cde”, string X has 2 unique characters and Y has 3 unique characters. 
X = “abc” and Y = “de”, string X has 3 unique characters and Y has 2 unique characters.
X = “abcd” and Y = “e”, string X has 4 unique characters and Y has 1 unique character.
Sample Input 2 :
2
codingninjas
codestudio
Sample Output 2 :
0
1
Hint

Can you take advantage of the small constraints?

Approaches (2)
Brute Force

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”.
Time Complexity

O( N ^ 2 ), where N denotes the length of the input string


We run a loop to generate all the possible splits, and for each split, we iterate the entire string to calculate the number of distinct characters.

Hence the time complexity is O( N^2 ).

Space Complexity

O( 1 )


Constant space is used to store the frequency array as the frequency array is of size ~O(26). Hence the space complexity is O( 1 ).

Code Solution
(100% EXP penalty)
Split the String
Full screen
Console