Split String

Easy
0/40
profile
Contributed by
106 upvotes
Asked in companies
QuikrAmazonUnacademy

Problem statement

You are given a string ‘str’ of even length. Your task is to find out if we divide the ‘str’ from the middle, will both the substrings contain an equal number of vowels or not.

For Example: 
You are given, ‘str’= ‘codingninjas’, when we split this string we get, ‘coding’ and ‘ninjas’ which both contain 2 vowels each. Hence the answer is ‘True’.
Detailed explanation ( Input/output format, Notes, Images )
Input Format: 
The first line of input contains a single integer ‘T’, representing the number of test cases.

The first line of each test case contains a string ‘str’ representing the given string.
Output Format: 
For each test case, print a "True” or “False" depending on if the halves of the string have an equal number of vowels or not.

Print a separate line for each test case.
Constraints: 
1 <= T <=  10
1 <= |str| <= 10^6

‘str’ will contain upper and lower case characters of the English alphabet.
|str| is even.
Time Limit: 1 sec.
Note : 
You do not need to print anything. It has already been taken care of. Just implement the given function.
Sample Input 1:
2
codingninjas
helloworld
Sample Output 2:
True
False
Explanation:
For the first test case, ‘str’= ‘codingninjas’, when we split this string we get, ‘coding’ and ‘ninjas’ which both contain 2 vowels each. Hence the answer is ‘True’.

For the second test case, ‘str’= ‘helloworld’, when we split this string we get ‘hello and ‘world’, which contain 2 and 1 vowels respectively. Hence the answer is ‘False’.
Sample Input 2:
2
Aa
AbbaaA
Sample Output 2:
True
False
Hint

Try to count the vowels in each half.

Approaches (1)
Split String

In this approach, we will count the number of vowels from each half of the string, For this, we will create a set of vowels in the English alphabet, both uppercase and lowercase and, iterate over the string.


 

Algorithm:

  • Initialize a set of vowels ‘vowels’
  • Set secondHalf as length of ‘str’ / 2
  • Set diff as 0
  • iterate i through 0 to secondHalf - 1
    • If str[i] is in vowels increase diff by 1
    • If str[i + secondHalf] is in vowels decrease diff by 1
  • Return true is diff is 0 else return false.
Time Complexity

O(N), Where N is the length of the string.

 

We are iterating over half of the string which will take O(N) time. Hence the final time complexity is O(N).

Space Complexity

O(1),

 

We are maintaining a set of vowels that will take constant space. Hence the final space complexity is O(1).

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