Justify Text

Hard
0/120
Average time to solve is 35m
22 upvotes
Asked in companies
GoogleAdobeWalmart

Problem statement

Given a sentence(in the form of an array of words), and an integer ‘L’, return an array of strings i.e a paragraph such that each line has exactly ‘L’ characters, and is left and right justified.

Justification of text means that space is added between words so that both edges of each line are aligned with both margins. The last line in the paragraph is aligned left.

One needs to add the maximum number of words in a line such that the number of lines is minimised.

We can add whitespaces in a line so that each line has exactly the same number of characters i.e L.

If the number of spaces on a line does not divide evenly between words, the empty slots on the left will be assigned more spaces than the slots on the right.

For the last line of text, it should be left justified and no extra space is inserted between words.

For example: 
Let the given sentence be: [ “what”, “must”, “be”, “shall”, “be.”]
And L=12.

The justified output will be :

[ “what must be”
“Shall be.”       ]

Note that the last line is only left justified.
Detailed explanation ( Input/output format, Notes, Images )
Input Format: 
The first line of input contains an integer ‘T’ representing the number of test cases. Then the test cases follow.
The first line of each test case contains a single integer ‘n’ denoting the number of words in the sentence.
The second line of each test case contains space separated strings denoting the word in the sentence. Note that no word has space in between it.
The third line of each test case contains the integer ‘L’ denoting the number of characters in each line in the justified output
Output Format: 
For each test case, return an array of strings denoting the justified output of the given sentence.
The output for each test case is in a separate line.
Note: 
1. You do not need to print anything; it has already been taken care of.
2. The words do not contain whitespaces.
3. It is guaranteed that L is always greater than the number of characters in any of the given words in the given array ‘words’
Constraints:
1 <= T <= 100
1 <= words.length <= 300
1 <= words[i].length <= 20
words[i] consists of only English letters and symbols.
1 <=L <= 100
words[i].length <= L


Where ‘T’ is the number of test cases, words.length denotes the number of words in the array and words[i].length denotes the number of alphabets in each word
L denotes the number of character in each line of the result.

Time Limit: 1 sec
Sample Input 1:
2
7
This is an example of text justification.
16
3
I like apple
6
Sample Output 1:
This    is    an
example  of text
justification. 
I like
apple
Explanation of Sample Input 1:
For the first test case, 
We have 7 words in the sentence and we can have 16 characters in each line. So we will have the output as given above.
In each line we need 16 characters, we see that the first 3 words have 4+2+2 =8 characters and add 2 gaps. I.e 10 characters. now if we take one more word i.e example, we exceed the total number of characters in the line so we can take only 3 characters. We have 8 characters and 8 spaces. Which need to be distributed between 2 gaps. So each gap will have 4 spaces.

For the second test case, 
We have 3 words in the sentence and 6 characters in each line. So we will have output as given above
Sample Input 2:
2
9
When there is a will there is a way
10
4
Coding ninjas is great
10
Sample Output 2:
 When there
 is  a will
 there is a
 way
 Coding    
 ninjas  is
 great
Hint

Try to put as many words as possible in a line and then insert spaces at appropriate places.

Approaches (1)
Brute Force
  • The key idea here is the fact we just need to greedily put as many words as possible in each line if the total number of characters in the line is less than or equal to L.\
  • Once we have the words to be inserted, we use a greedy approach to fit the most words less than max-width and to fit the most spaces in the least number of gaps after adjusting the gaps for uniform space.
  • We can use the following algorithm:

        1. Find all words whose combined width( accounting for the gap of one for each word) is less than L.

        2. Find the total padding which can be added to each word to make the whole container width equal to L.

        3. Find the extra padding and append it uniformly to the first few words.

        4. Append the spaces to every word in the list except the last.

        5. Return final result.


 

Using the above algorithm we can have the following approach:

  • We define the following variables:
  • startIndex -> used for tracking gaps from the first word in our  list to current word
  • currWords -> stores all words whose combined width (gaps inclusive) is less than maxWidth
  • paddings -> list of " " string for each word in our list, which will be appended to       each word prior to returning the final result
  • Result -> stores the final result
  • currIndex -> index of the word we are currently working within our array
  • We take a loop traversing our ‘words’ array and count the number of gaps which is the difference between currentIndex and StartIndex-1 as 2 words will have 1 gap 3 words will have 2 gaps and so on.
  • We also check if current index is the last word.
  • Now, if the current word plus gaps is less than L we add more words.
  • Otherwise, we make variable ‘numWords’ which stores a number of words in the line and We find the number of spaces in each gap by simply dividing the total spaces by the number of gaps and padding them after each word in the line.
  • The remainder is padded to the right of the line.
  • Finally, we push this newly formed string in the array ‘res’
  • Once we have traversed all the words we return ‘res’.
Time Complexity

O(N ), where ‘N’ is the size of the given array.

 

We need to traverse all the words in the array

Space Complexity

O(N), where ‘N’ is the size of the given array.

 

We need ‘res’ which has n strings.

Code Solution
(100% EXP penalty)
Justify Text
Full screen
Console