Divide String

Moderate
0/80
Average time to solve is 15m
profile
Contributed by
12 upvotes
Asked in companies
Spring FestSpringworksGoogle inc

Problem statement

Ninja has been given a string ‘WORD’ containing lower case alphabets. Ninja wants to know all the strings by dividing ‘WORD’ into ‘N’ strings of equal length.

For Example:

For ‘WORD’ =  “abcdefgh”, ‘N’ = 2. Following are the 2 strings of length 4.

“abcd”
“efgh”

Can you help Ninja to get all the strings from ‘WORD’ by dividing them into equal parts?

Detailed explanation ( Input/output format, Notes, Images )
Input Format: 
The first line of input contains an integer 'T' which denotes the number of test cases or queries to be run. Then the test cases follow.

The first line of each test case contains a string ‘WORD’ and an integer ‘N’.
Output Format : 
For each test case, print all strings that can be formed from ‘WORD’ by dividing it into ‘N’ equal parts.

Return empty string array/list if it is not possible to divide ‘WORD’ into ‘N’ equal length strings.

Print the output of each test case in a separate line.
Note: 
You do not need to print anything; it has already been taken care of. Just implement the given function.
Constraints: 
1 <= ‘T’ <= 100
‘WORD’ = Lower case english alphabet
1 <= |WORD| <= 2000
1 <= ‘N’ <= |WORD|

Time Limit: 1 second
Sample Input 1:
2
asdfghjkl 3
codingninjas 5
Sample Output 1:
asd fgh jkl
Explanation For Sample Output 1:
For the first test case:
Given ‘WORD’ = “asdfghjkl” can be divided into 3 strings each of length 3. 

Following are the possible strings of length 3.
1. “asd”
2. “fgh”
3. “jkl”  

For the second test case:
Given ‘WORD’ = “codingninjas”, it is impossible to divide this ‘WORD’ into 5 strings of equal length. 

So we return an empty array/list.
Sample Input 2:
2   
a 1
code 4
Sample Output 2:
a
c o d e
Hint

Try to use the brute force approach to generate all strings.

Approaches (1)
Brute Force

First, check if the ‘WORD’ can be divided into ‘N’ strings of equal length or not.

 

  • Check if the length of ‘WORD’ is a multiple of ‘N’ or not.
    • If ‘WORD’ is not a multiple of ‘N’ it means we can not divide ‘WORD’ into ‘N’ equal length strings and we simply return -1.

 

Calculate the possible length ‘len’ of  ‘N’ equal length strings.After getting the length, iterate the ‘WORD’ and for each substring of length ‘len’ starting from index 0 print the substring.

 

 

Here is the complete Algorithm:

 

  • Initialize an array/list ‘answer’ of type string to store the final output.
  • If ‘|WORD| % N’ is not equal to zero then return ‘answer’.
  • Initialize ‘len’ = ‘|WORD| / N’ and a string ‘temp’ = “”.
  • Run a for loop from ‘i’ = 0 to ‘|WORD|’ and for each ‘i’ do the following:
    • If ‘i’ % ‘len’ is equal to 0 and the length of ‘temp' is not 0 then do the following:
      • Insert ‘temp’ into the ‘answer’ and empty the ‘temp’.
    • Push ‘WORD[i]’ to ‘temp’.
  • Finally insert 'temp' to the ‘answer’ and return ‘answer’.
Time Complexity

O(|WORD|), where |WORD| is the length of the string ‘WORD’.

 

Because in the worst case we are iterating each character of the ‘WORD’ exactly once. Hence the overall time complexity will be |WORD|.

Space Complexity

O(1).

 

Because we are not using any extra space.

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