# Text Justification | LeetCode | InterviewBit | Solution Explained

Text Justification LeetCode/Justified Text InterviewBit is a interesting problem. I use raw logic to explain the solution in detail. Problem Links: LeetCode 68. Text Justification InterviewBit Justified Text.

## 0. Text Justification: Problem Discussion

### 0.0. IO Format

• inputs: words (a list of words), maxWidth (max width of a sentence)
• output: list of strings of each maxWidth length
• constraints:
• pack as many words in the line as possible
• add spaces to evenly space out the words
• number of spaces must be the same between words
• (add remaining spaces to the left) #left_spaces >= #right_spaces
• last row is left justified

### 0.1. Example

The constraints are a bit tricky to understand, so let’s take an example.

The answer in this case is given as such:

• We see that we can efficiently pack “this” “is” and “an” in the first row, but we can’t fit “example”, even with 1 spacing. So, we just have the first 3 words and space them out equally.
• Since “example” was sent to the second row, we start with that. We are able to add “of” and “text” too, but not “justification”. We then add the appropriate spaces between. Since there are 3 total spaces, we give left space one more than right.
• finally, last row is simply left justified.

## 1. Text Justification: Observations & Logic

### 1.0. Intuitions

This question is amazing. It only requires basic knowledge of how strings work, and the rest is implementation. We can start following the rules and you’ll be amazed at how simple the answer is.

### 1.1. Observations

We can only decide the amount of spaces once we have decided what words to put in a row.

part 1: find the right number of words

1. find what all words we can pack in a row. assume minimal space of 1 for now.
2. generate an intermediate list of all such rows, containing the correct amount of words

part 2: find the right number of spaces

1. find the number of spaces required `(maxWidth - sum(len(word) for word in row))`
2. distribute the spacers in (almost) equal amounts to the `spaces/(len(row)-1)`
3. last line just gets one space between words, and remaining length of maxWidth is spaces.

## 2. Text Justification: Implementation

### 2.0. Code

```class Solution:
def fullJustify(self, words: List[str], maxWidth: int) -> List[str]:
# get the words, ensuing min rows consumed (greedily)
rows = [""]
for word in words:
# if emplty row, add item by default
if not rows[-1]: rows[-1] += word
# if can add one more word, do so
elif len(rows[-1]) + 1 + len(word) <= maxWidth: rows[-1] += " " + word
# else, create a new row
else: rows.append(word)

# get a list of words instead (spaces dont matter right now)
word_rows = [row.split() for row in rows]

spaced_rows = []
# fix the spaces
for row in word_rows[:-1]:
spaces = maxWidth - sum(len(word) for word in row)

# if only one word, life is easy
if len(row) == 1:
spaced_rows.append(row[0] + " "*spaces)
# for multiple words,
else:
# get the divisor and remainder
# think why we use len(row)-1 :0
d, r = divmod(spaces, len(row)-1)
temp = ""

for word in row:
# if some extra spaced remaining, consume them
if r:
temp += word + " "*(d + 1)
r -= 1
else:
temp += word + " "*d
# remove the last couple of spaces
spaced_rows.append(temp.strip())

# the last row has single spaced words
spaced_rows.append(" ".join(word_rows[-1]))
# dummy number of spaces to fill up till maxWidth
spaced_rows[-1] += " "*(maxWidth - len(spaced_rows[-1]))
return spaced_rows
```

### 2.1. Complexity Analysis

• Time: O(len(words) * maxWidth + len(rows) * maxWidth) for the part 1 and part 2 respectively
• Space: O(len(rows) + len(word_rows) + len(spaced_rows)) = O(len(rows)).
##### Tanishq Chaudhary

Producing high-quality intuitive explanations of interview problems. Currently covering LeetCode and InterviewBit.

### Recommended Posts

##### Gas Station | InterviewBit | Solution Explained

June 13, 2022

##### Majority Element | InterviewBit | Solution Explained

June 13, 2022

##### Assign Mice to Holes | InterviewBit | Solution Explained

June 13, 2022

#### Comments

1. Please write the proof.

2. This solution need an amendment for 2 digit number.

3. Please write a Proof for this

4. Matt Michael D’Agati is the founder of Renewables Worldwide, an Solar Firm in MA.

A few age ago, taking a leap of faith, Matt D’Agati delved into the realm of solar, and/or in a short occasion commenced effectively marketing significant amounts of power, primarily around the business industry, collaborating with solar farm developers and local businesses in the “design” of their unique plans.

Ongoing marketing within the sector, offered Matthew to participate a regional startup two years in the, and in a short time, he assumed the role of their Chief Strategy Officer, in charge of all operation and endeavor improvement, in addition to being marketed social group property.

To planned unions and shear get the job done mentality, Matthew D’Agati brought that firm from an initial initial-year revenue to in excess of a 2 hundred% surge in overall money by yr two. Based on that foundation, RW, a experienced-operated company, was produced with goal of giving you alternative electrical remedies for a more intelligent and more sustainable future.

Even more mainly, recognizing there is an untapped market in the market place and an improved approach to realize final results, RW is one of a handful of manufactures in the u.s. to place emphasis on individual acquire, concentrating in both industrial and home solar-powered town off-take. Its visualization is to make a purchases commercial infrastructure on a community-based, statewide, countrywide level, offering various sustainable fuel goods within the of RW.

This enthusiasm in the actual sustainable industry goes on to stimulate and inspire Matthew in enduring his solicit to work with institutions that have the unchanging of offering limitless fuel tips for a a whole lot more ecological destiny. Matt has already a new in companies from Hesser College.

This site uses Akismet to reduce spam. Learn how your comment data is processed.