Format the text so that each line has precisely W characters, left and right justified, given an array of strings arr[] and a width W. Put as many words as you can in each line, try to divide the additional spaces evenly, and if they don’t divide evenly, put more spaces to the left. There should be no extra spaces between words in the final line, which should be left-justified.
For instance:
Input: arr[] = {“GfG”, “is”, “the”, “best”, “computer”, “science”, “portal”, “for”, “geeks.”}, W = 16
Output:
{
“GfG is the best”,
“computer science”,
“portal for”,
“geeks. “
}
Arr[] = {"GfG", "is", "the", "best", "computer", "science", "portal", "for", "geeks."}, W = 16 is the input.
The output is: "GfG is the best," "computer science," "portal for," and "geeks."
Justification: The text must be justified so that each line has precisely 16 characters and is evenly justified.
The first line's total character count is 12 (including spaces: 12 + 3 = 15) = "GfG" (3) + "is" (2) + "the" (3) + "best" (4). We add one more space between "GfG" and "is" because we need one more space and all additional spaces should be added from left to right.
The second line's total character count is 15 (including spaces: 15 + 1 = 16) = "computer" (8) + "science" (7). There's no need for additional spaces.
The third line has a total of nine characters (including spaces): "portal" (6) + "for" (3) = 10. We shall insert the six extra spaces between "portal" and "for" since we need to add them.
The fourth line's total character count is "geeks." (6) = 6. We will add the final ten spaces at the end because the final line needs to be left justified.
W = 11; input: arr[] = {"The", "quick", "brown", "fox", "jumps", "over", "the", "lazy", "dog."}
The output is: { "The quick," "brown fox," "jumps over," "the lazy," and "dog."
Output:
{
“The quick”,
“brown fox”,
“jumps over”,
“the lazy”,
“dog. “
}Method:
The initial step is to decide which words, with one space between each pair of words, can be put into each line. Each line must be justified after the words have been chosen.
The total length of the words that are contained, separated by one space, must be less than or equal to W in order for a line to be justified. Additionally, if the current line is the text’s last line, we must add spaces to it so that its width equals W. If not, count the number of spaces required to make each line W long and evenly distribute them if the current line is not the last line.
C++
// 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 = {"Sky", "is", "the", "best", "computer",
"science", "portal", "for", "Webz."} ;
int W = 16;
vector<string> ans = justifyText(arr, W);
for (int i = 0; i < ans.size(); i++)
cout << ans[i] << "\n";
return 0;
}Java
// 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("Sky", "is", "the", "best",
"computer", "science", "portal", "for", "Webz." );
int W = 16;
List<String> ans = justifyText(arr, W);
for (String line : ans)
System.out.println(line);
}
}Python
# 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 = ["Sky", "is", "the", "best", "computer",
"science", "portal", "for", "Webz."]
W = 16
ans = justify_text(arr, W)
for line in ans:
print(line)C#
// 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 = {
"Sky", "is", "the", "best", "computer",
"science", "portal", "for", "Webz."
};
int W = 16;
List<string> ans = JustifyText(arr, W);
foreach (string line in ans) {
Console.WriteLine(line);
}
}
}JS
// 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 = ["Sky", "is", "the", "best", "computer",
"science", "portal", "for", "webz."];
let W = 16;
let ans = justifyText(arr, W);
for (let line of ans) {
console.log(line);
}Output
Sky is the best
computer science
portal for
Webz.
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.