Text Justification LeetCode Solution

We will discuss Text Justification LeetCode Solution today

Problem Statement

The problem “Text Justification” states that you are given a list s[ ] of type string of size n and an integer size. Justify the text such that each line of text consists of size number of characters. You can use space(‘ ‘) as a character to complete the required number of characters in a line.

Example

s = {"TutorialCup", "is", "the", "best", "portal", "for", "programming."}
size = 12

TutorialCup
is  the best
portal   for
programming.

Explanation: As we can use spaces between the words, we have placed them properly as can be seen in the image embedded above.

s = {"This", "article", "is", "contributed", "by", "Akshita", "Jain"}
size = 13

This  article
is
contributed
by    Akshita
Jain

Algorithm for Text Justification LeetCode Solution

1. Initialize a list s[ ] of type string of size n and an integer variable size.
2. Traverse through the list and check for each word/string if the length of the current word is less than or equal to the given size, add the current word to the result.
3. Else if the length of the current string/word is greater than the given size, use the white spaces to complete the remaining positions of the line.
4. If the sum of the length of the next word in the same line and the length of the previous word in the same line is less than or equal to the given size, add the current word to the result and adjust the remaining places with the white space.
5. Else if the sum of the length of the next word in the same line and the length of the previous word in the same line is greater than the given size, add the current word in the next line of the result and fill the remaining places of current line with the white space.
6. Print the resulting string.

Code

C++ Program of Text Justification

#include "bits/stdc++.h" 
using namespace std; 
  
string getSpaces(int n){
    string s = "";
    for(int i=0; i<n;i++) s += " ";
    return s; 
}

string getLine(vector<string>& words, int start, int end, int letterCount, int maxWidth){
    string res = words[start];
    int spaces = maxWidth - letterCount;
    
    if(start == end){ 
        res += getSpaces(spaces);
        return res;
    }
    
    int numOfSpace = spaces/(end-start);
    int extraOne = spaces%(end-start);
    string space0 = getSpaces(numOfSpace);
    string space1 = space0 + " "; 
    
    for(int i= 0; i< end-start; i++){
        res  = res + (i < extraOne? space1: space0) + words[start + 1 + i];
    }
    return res; 
}

vector<string> fullJustify(vector<string>& words, int maxWidth) {
    int N = words.size(); 
    int i = 0, j = 0;
    int counter = 0; 
    vector<string> res; 
    
    while(i<N && j<N){
        int len = words[j].length(); 
        counter += len;
        
        if(counter + j - i > maxWidth){
            counter -= len; 
            res.push_back(getLine(words, i, j-1, counter, maxWidth));
            i = j; 
            counter = 0; 
        }
        
        else{
            j++;
        }
    }
    
    if(counter){
        string last = words[i];
        
        for(int x=i+1; x < j; x++){ 
            last = last + " " + words[x];
        }
        
        last = last + getSpaces(maxWidth - last.size());
        res.push_back(last);
    }

    return res; 
}

int main(){
    vector<string> s = {"TutorialCup", "is", "the", "best", "portal", "for", "programming."};
    int size = 12;
    
    vector<string> lines = fullJustify(s, size); 
    
    for(auto x: lines)
        cout << x << endl;
    
    return 0; 
}

TutorialCup 
is  the best
portal   for
programming.

Java Program of Text Justification

import java.util.*;

class TextJustification{
    
    static List<String> fullJustify(String[] words, int maxWidth) {
        List<String> res = new ArrayList<>();
        int size = words.length;
        int index = 0;
        
        while (index < size){
            int totalChars = words[index].length();
            int lastIndex = index + 1;
            int gaps = 0;
            
            while (lastIndex < size){
                if (totalChars + 1 + words[lastIndex].length() > maxWidth){
                    break;
                }
                totalChars += 1 + words[lastIndex++].length();
                gaps++;
            }
            
            StringBuilder sb = new StringBuilder();
            
            if (lastIndex == size || gaps == 0){
                for (int i = index; i < lastIndex; ++i){
                    sb.append(words[i]).append(' ');
                }
                sb.deleteCharAt(sb.length() - 1);
                while (sb.length() < maxWidth){
                    sb.append(' ');
                }
            } 
            
            else {
                int spaces = (maxWidth - totalChars) / gaps;
                int restSpaces = (maxWidth - totalChars) % gaps;
                for (int i = index; i < lastIndex - 1; ++i){
                    sb.append(words[i]).append(' ');
                    for (int j = 0; j < spaces + (i - index < restSpaces ? 1 : 0); ++j){
                        sb.append(' ');
                    }
                }
                sb.append(words[lastIndex - 1]);
            }
            
            res.add(sb.toString());
            index = lastIndex;
        }
        return res;
    }
  
  public static void main (String[] args){
      
      String[] words = {"TutorialCup", "is", "the", "best", "portal", "for", "programming."};
      int size = 12;
      
      List<String> res = new ArrayList<String>();
      res = fullJustify(words, size);
      ListIterator<String> lItr = res.listIterator();
      
      while (lItr.hasNext()){
          System.out.println(lItr.next());
      }
  }
}
  

TutorialCup 
is  the best
portal   for
programming.

Complexity Analysis

Time Complexity

O(n) where n is size of the given string array s[ ]. We are running a while loop inside fullJustify which runs only until either of the i and j variable do not cross N. And this loop takes linear time to end. Thus time complexity is linear.

Space Complexity

O(n) because we used space to store n string.