Given an array of strings arr[] and a width W, format the text so each line has exactly W characters, left and right justified. Place as many words as possible per line, distribute extra spaces as evenly as possible, and assign more spaces to the left if they don't divide evenly. The last line should be left-justified with no extra spaces between words.
Examples:
Input: arr[] = {"GfG", "is", "the", "best", "computer", "science", "portal", "for", "geeks."}, W = 16
Output:
{
"GfG is the best",
"computer science",
"portal for",
"geeks. "
}
Explanation: We need to justify the text such that each line has exactly 16 characters and should be equally justified.
- Total characters in first line: "GfG" (3) + "is" (2) + "the" (3) + "best" (4) = 12 (including spaces: 12 + 3 = 15). Since, we need 1 more space and all the extra spaces should be added from left to right, we add 1 extra space between "GfG" and "is".
- Total characters in second line: "computer" (8) + "science" (7) = 15 (including spaces: 15 + 1 = 16). No need to add extra spaces.
- Total characters in third line: "portal" (6) + "for" (3) = 9 (including spaces = 9 + 1 = 10). Since, we need to add 6 extra spaces, we will add them between "portal" and "for".
- Total characters in fourth line: "geeks." (6) = 6. Since we need 10 extra spaces and the last line should be left justified, we will add them at the end.
Input: arr[] = {"The", "quick", "brown", "fox", "jumps", "over", "the", "lazy", "dog."}, W = 11
Output:
{
"The quick",
"brown fox",
"jumps over",
"the lazy",
"dog. "
}
Approach:
The idea is to first select the words that can be inserted in each line including a single space between every pair of words. After selecting the words for each line, we need to justify the line.
To justify a line, the sum of length of included words with one space between them should be less than or equal to W. Also, if the current line is the last line of the text, then we need to append spaces to make the width of line equal to W. Otherwise, if the current line is not the last line then count the number of spaces needed to make the length of each line W and distribute the spaces evenly.
Below is the implementation of the approach:
// C++ program to Justify the given Text
// according to the given width of each line
#include <bits/stdc++.h>
using namespace std;
// function to count the characters from arr[start] to
// arr[end], both start and end inclusive
int countCharacters(int start, int end, vector<string> &arr) {
int cnt = 0;
for (int i = start; i <= end; i++)
cnt += arr[i].length();
return cnt;
}
// function to fill the end of str with spaces
string padLine(string &str, int W) {
int len = str.length();
for (int i = 0; i < W - len; i++)
str.push_back(' ');
return str;
}
// function to form a line using all the words in range [start, end]
// and justify the line to push it to the result
string justify(int start, int end, vector<string> &arr, int W) {
string justifiedLine = "";
int wordsCnt = end - start + 1;
// If the line has only 1 word, then pad it with spaces and return it
if (wordsCnt == 1)
return padLine(arr[start], W);
int spaceCnt = W - countCharacters(start, end, arr);
string space = " ";
int extraSpaces = 0;
// If the line is not the last line, then all words should have
// even spaces between them and all the extra spaces will be
// added to the spaces to the left
if (end != arr.size() - 1) {
space = string(spaceCnt / (wordsCnt - 1), ' ');
extraSpaces = spaceCnt % (wordsCnt - 1);
}
for (int i = start; i <= end; i++) {
// Add the word to the justified line
justifiedLine.append(arr[i]);
// add spaces to the justified line
justifiedLine.append(space);
// If there are extra spaces, add it to the spaces to the left
if (extraSpaces > 0) {
justifiedLine.push_back(' ');
extraSpaces -= 1;
}
}
// Remove extra spaces from the right end
while (justifiedLine.length() > W)
justifiedLine.pop_back();
// Pad line with spaces if we have empty space to the right
return padLine(justifiedLine, W);
}
// function to get the end index such that all the words from
// start to end can be placed in one line
int getEnd(int start, vector<string> &arr, int W) {
int end = start + 1;
int len = arr[start].length();
while (end < arr.size() && (len + 1 + arr[end].length()) <= W) {
len += arr[end].length() + 1;
end += 1;
}
return end - 1;
}
// function to combine the words to each line and justify the line
// from both sides
vector<string> justifyText(vector<string> &arr, int W) {
int start = 0, end;
vector<string> justifiedText;
while (start < arr.size()) {
// find the ending index such that words in the range
// [start, end] can be put in a single line
end = getEnd(start, arr, W);
// Form a line using words from start to end and justify it
string justifiedLine = justify(start, end, arr, W);
// Push the justified line to the result
justifiedText.push_back(justifiedLine);
start = end + 1;
}
return justifiedText;
}
int main() {
vector<string> arr = {"GfG", "is", "the", "best", "computer",
"science", "portal", "for", "geeks."} ;
int W = 16;
vector<string> ans = justifyText(arr, W);
for (int i = 0; i < ans.size(); i++)
cout << ans[i] << "\n";
return 0;
}
// Java program to justify the given text
// according to the given width of each line
import java.util.ArrayList;
import java.util.List;
public class GFG {
// function to count the characters from arr[start] to
// arr[end], both start and end inclusive
static int countCharacters(int start, int end,
List<String> arr) {
int cnt = 0;
for (int i = start; i <= end; i++)
cnt += arr.get(i).length();
return cnt;
}
// function to fill the end of str with spaces
static String padLine(String str, int W) {
int len = str.length();
StringBuilder sb = new StringBuilder(str);
for (int i = 0; i < W - len; i++)
sb.append(' ');
return sb.toString();
}
// function to form a line using all the words in range [start, end]
// and justify the line to push it to the result
static String justify(int start, int end, List<String> arr, int W) {
StringBuilder justifiedLine = new StringBuilder();
int wordsCnt = end - start + 1;
// If the line has only 1 word, then pad it with spaces and return it
if (wordsCnt == 1)
return padLine(arr.get(start), W);
int spaceCnt = W - countCharacters(start, end, arr);
String space = " ";
int extraSpaces = 0;
// If this line is not the last line, then all the words should
// have even spaces between them and all the extra spaces will
// be added to the spaces to the left
if (end != arr.size() - 1) {
space = new String(new char[spaceCnt / (wordsCnt - 1)])
.replace('\0', ' ');
extraSpaces = spaceCnt % (wordsCnt - 1);
}
for (int i = start; i <= end; i++) {
// Add the word to the justified line
justifiedLine.append(arr.get(i));
// add spaces to the justified line
justifiedLine.append(space);
// If there are extra spaces, add it to the spaces to the left
if (extraSpaces > 0) {
justifiedLine.append(' ');
extraSpaces -= 1;
}
}
// Remove extra spaces from the right end
while (justifiedLine.length() > W)
justifiedLine.setLength(justifiedLine.length() - 1);
// Pad line with spaces if we have empty space to the right
return padLine(justifiedLine.toString(), W);
}
// function to get the end index such that all the words from
// start to end can be placed in one line
static int getEnd(int start, List<String> arr, int W) {
int end = start + 1;
int len = arr.get(start).length();
while (end < arr.size() && (len + 1 + arr.get(end).length()) <= W) {
len += arr.get(end).length() + 1;
end += 1;
}
return end - 1;
}
// function to combine the words to each line and justify the line
// from both sides
static List<String> justifyText(List<String> arr, int W) {
int start = 0;
List<String> justifiedText = new ArrayList<>();
while (start < arr.size()) {
// find the ending index such that words in the range
// [start, end] can be put in a single line
int end = getEnd(start, arr, W);
// Form a line using words from start to end and justify it
String justifiedLine = justify(start, end, arr, W);
// Push the justified line to the result
justifiedText.add(justifiedLine);
start = end + 1;
}
return justifiedText;
}
public static void main(String[] args) {
List<String> arr = List.of("GfG", "is", "the", "best",
"computer", "science", "portal", "for", "geeks." );
int W = 16;
List<String> ans = justifyText(arr, W);
for (String line : ans)
System.out.println(line);
}
}
# Python program to justify the given text
# according to the given width of each line
# function to count the characters from arr[start] to
# arr[end], both start and end inclusive
def count_characters(start, end, arr):
cnt = 0
for i in range(start, end + 1):
cnt += len(arr[i])
return cnt
# function to fill the end of str with spaces
def pad_line(s, W):
len_s = len(s)
return s + ' ' * (W - len_s)
# function to form a line using all the words in range [start, end]
# and justify the line to push it to the result
def justify(start, end, arr, W):
justified_line = ""
words_cnt = end - start + 1
# If the line has only 1 word, then pad it with spaces and return it
if words_cnt == 1:
return pad_line(arr[start], W)
space_cnt = W - count_characters(start, end, arr)
space = " "
extra_spaces = 0
# If the line is not the last line, then all words should have
# even spaces between them and all the extra spaces will be
# added to the spaces to the left
if end != len(arr) - 1:
space = ' ' * (space_cnt // (words_cnt - 1))
extra_spaces = space_cnt % (words_cnt - 1)
for i in range(start, end + 1):
# Add the word to the justified line
justified_line += arr[i]
# add spaces to the justified line
if i < end:
justified_line += space
# If there are extra spaces, add it to the spaces to the left
if extra_spaces > 0:
justified_line += ' '
extra_spaces -= 1
# Remove extra spaces from the right end
justified_line = justified_line[:W]
# Pad line with spaces if we have empty space to the right
return pad_line(justified_line, W)
# function to get the end index such that all the words from
# start to end can be placed in one line
def get_end(start, arr, W):
end = start + 1
len_words = len(arr[start])
while end < len(arr) and (len_words + 1 + len(arr[end])) <= W:
len_words += len(arr[end]) + 1
end += 1
return end - 1
# function to combine the words to each line and justify the line
# from both sides
def justify_text(arr, W):
start = 0
justified_text = []
while start < len(arr):
# find the ending index such that words in the range
# [start, end] can be put in a single line
end = get_end(start, arr, W)
# Form a line using words from start to end and justify it
justified_line = justify(start, end, arr, W)
# Push the justified line to the result
justified_text.append(justified_line)
start = end + 1
return justified_text
if __name__ == "__main__":
arr = ["GfG", "is", "the", "best", "computer",
"science", "portal", "for", "geeks."]
W = 16
ans = justify_text(arr, W)
for line in ans:
print(line)
// C# program to Justify the given Text
// according to the given width of each line
using System;
using System.Collections.Generic;
using System.Text;
class GfG {
// Function to count the characters from arr[start] to
// arr[end], both start and end inclusive
static int CountCharacters(int start, int end, string[] arr) {
int cnt = 0;
for (int i = start; i <= end; i++)
cnt += arr[i].Length;
return cnt;
}
// Function to fill the end of str with spaces
static string PadLine(string str, int W) {
int len = str.Length;
StringBuilder sb = new StringBuilder(str);
for (int i = 0; i < W - len; i++) {
sb.Append(' ');
}
return sb.ToString();
}
// Function to form a line using all the words in range [start, end]
// and justify the line to push it to the result
static string Justify(int start, int end, string[] arr, int W) {
StringBuilder justifiedLine = new StringBuilder();
int wordsCnt = end - start + 1;
// If the line has only 1 word, then pad it with spaces and return it
if (wordsCnt == 1)
return PadLine(arr[start], W);
int spaceCnt = W - CountCharacters(start, end, arr);
string space = " ";
int extraSpaces = 0;
// If the line is not the last line, then all words should have
// even spaces between them and all the extra spaces will be
// added to the spaces to the left
if (end != arr.Length - 1) {
space = new string(' ', spaceCnt / (wordsCnt - 1));
extraSpaces = spaceCnt % (wordsCnt - 1);
}
for (int i = start; i <= end; i++) {
// Add the word to the justified line
justifiedLine.Append(arr[i]);
// Add spaces to the justified line
if (i < end) {
justifiedLine.Append(space);
// If there are extra spaces, add it to the spaces to the left
if (extraSpaces > 0) {
justifiedLine.Append(' ');
extraSpaces -= 1;
}
}
}
// Remove extra spaces from the right end
if (justifiedLine.Length > W)
justifiedLine.Length = W;
// Pad line with spaces if we have empty space to the right
return PadLine(justifiedLine.ToString(), W);
}
// Function to get the end index such that all the words from
// start to end can be placed in one line
static int GetEnd(int start, string[] arr, int W) {
int end = start + 1;
int len = arr[start].Length;
while (end < arr.Length && (len + 1 + arr[end].Length) <= W) {
len += arr[end].Length + 1;
end += 1;
}
return end - 1;
}
// Function to combine the words to each line and justify the line
// from both sides
static List<string> JustifyText(string[] arr, int W) {
int start = 0;
List<string> justifiedText = new List<string>();
while (start < arr.Length) {
// Find the ending index such that words in the range
// [start, end] can be put in a single line
int end = GetEnd(start, arr, W);
// Form a line using words from start to end and justify it
string justifiedLine = Justify(start, end, arr, W);
// Push the justified line to the result
justifiedText.Add(justifiedLine);
start = end + 1;
}
return justifiedText;
}
static void Main() {
string[] arr = {
"GfG", "is", "the", "best", "computer",
"science", "portal", "for", "geeks."
};
int W = 16;
List<string> ans = JustifyText(arr, W);
foreach (string line in ans) {
Console.WriteLine(line);
}
}
}
// JavaScript program to Justify the given Text
// according to the given width of each line
// Function to count the characters from arr[start] to
// arr[end], both start and end inclusive
function countCharacters(start, end, arr) {
let cnt = 0;
for (let i = start; i <= end; i++) {
cnt += arr[i].length;
}
return cnt;
}
// Function to fill the end of str with spaces
function padLine(str, W) {
let len = str.length;
while (len < W) {
str += ' ';
len++;
}
return str;
}
// Function to form a line using all the words in range [start, end]
// and justify the line to push it to the result
function justify(start, end, arr, W) {
let justifiedLine = "";
let wordsCnt = end - start + 1;
// If the line has only 1 word, then pad it with spaces and return it
if (wordsCnt === 1) {
return padLine(arr[start], W);
}
let spaceCnt = W - countCharacters(start, end, arr);
let space = " ";
let extraSpaces = 0;
// If the line is not the last line, then all words should have
// even spaces between them and all the extra spaces will be
// added to the spaces to the left
if (end !== arr.length - 1) {
space = " ".repeat(spaceCnt / (wordsCnt - 1));
extraSpaces = spaceCnt % (wordsCnt - 1);
}
for (let i = start; i <= end; i++) {
// Add the word to the justified line
justifiedLine += arr[i];
// Add spaces to the justified line
if (i < end) { // Avoid adding space after the last word
justifiedLine += space;
// If there are extra spaces, add them to the spaces to the left
if (extraSpaces > 0) {
justifiedLine += ' ';
extraSpaces--;
}
}
}
// Remove extra spaces from the right end
if (justifiedLine.length > W) {
justifiedLine = justifiedLine.slice(0, W);
}
// Pad line with spaces if we have empty space to the right
return padLine(justifiedLine, W);
}
// Function to get the end index such that all the words from
// start to end can be placed in one line
function getEnd(start, arr, W) {
let end = start + 1;
let len = arr[start].length;
while (end < arr.length && (len + 1 + arr[end].length) <= W) {
len += arr[end].length + 1;
end++;
}
return end - 1;
}
// Function to combine the words to each line and justify the line
// from both sides
function justifyText(arr, W) {
let start = 0;
let justifiedText = [];
while (start < arr.length) {
// Find the ending index such that words in the range
// [start, end] can be put in a single line
let end = getEnd(start, arr, W);
// Form a line using words from start to end and justify it
let justifiedLine = justify(start, end, arr, W);
// Push the justified line to the result
justifiedText.push(justifiedLine);
start = end + 1;
}
return justifiedText;
}
let arr = ["GfG", "is", "the", "best", "computer",
"science", "portal", "for", "geeks."];
let W = 16;
let ans = justifyText(arr, W);
for (let line of ans) {
console.log(line);
}
Output
GFG is the best computer science portal for geeks.
Time Complexity: O(N), where N is the sum of length of all words.
Auxiliary Space: O(W), where W is the max width of a line.