public class Solution {
public List<String> fullJustify(String[] words, int L) {
List<String> lines = new ArrayList<String>();
int index = 0;
while (index < words.length) {
int count = words[index].length();
int last = index + 1;
while (last < words.length) {
if (words[last].length() + count + 1 > L) break;
count += words[last].length() + 1;
last++;
}
StringBuilder builder = new StringBuilder();
int diff = last  index  1;
// if last line or number of words in the line is 1, leftjustified
if (last == words.length  diff == 0) {
for (int i = index; i < last; i++) {
builder.append(words[i] + " ");
}
builder.deleteCharAt(builder.length()  1);
for (int i = builder.length(); i < L; i++) {
builder.append(" ");
}
} else {
// middle justified
int spaces = (L  count) / diff;
int r = (L  count) % diff;
for (int i = index; i < last; i++) {
builder.append(words[i]);
if (i < last  1) {
for (int j = 0; j <= (spaces + ((i  index) < r ? 1 : 0)); j++) {
builder.append(" ");
}
}
}
}
lines.add(builder.toString());
index = last;
}
return lines;
}
}
Simple Java Solution


How about this?
public class Solution { public List<String> fullJustify(String[] words, int L) { final StringBuilder sb = new StringBuilder(); for (int i = 0; i < L; ++i) { sb.append(" "); } final String pads = sb.toString(); final List<String> strs = new ArrayList<>(); for (int i = 0, sum = 0, j = 0; i < words.length; i = j) { for (j = i + 1, sum = words[i].length(); j < words.length && sum + j  i + words[j].length() <= L; ++j) { sum += words[j].length(); } final StringBuilder l = new StringBuilder(); final int n = j  1  i; final int m = (j == words.length  0 == n) ? 1 : ((L  sum) / n); final int b = (j == words.length) ? 0 : (L sum  m * n); for (int k = i; k < j  1; ++k) { l.append(words[k]); l.append(pads.substring(0, (k  i < b) ? (m + 1) : m)); } l.append(words[j  1]); if (j == words.length  0 == n) { l.append(pads.substring(0, L  sum  n)); } strs.add(l.toString()); } return strs; } }

@sandeep37 when the spaces can not be divided evenly in a line between words, the empty slot on the left will be assigned more space than that on the right. For example, the extra spaces is 5, the diff = 2 (3 words), r will be 2 (5%2), spaces = 2 (5/2), then the first space slot will get 3 spaces and the second space slot will get 2 spaces. Please point out if I am wrong.

I just cleaned up the solution. It was getting a bit tricky in the original post when it was middle justified.
public class Solution { public List<String> fullJustify(String[] words, int L) { List<String> lines = new ArrayList<String>(); int index = 0; while (index < words.length) { int count = words[index].length(); int last = index + 1; while (last < words.length) { if (words[last].length() + count + 1 > L) break; //plus one for the space, if its a perfect fit it will fit count += 1 + words[last].length(); last++; } StringBuilder builder = new StringBuilder(); builder.append(words[index]); int diff = last  index  1; // if last line or number of words in the line is 1, leftjustified if (last == words.length  diff == 0) { for (int i = index+1; i < last; i++) { builder.append(" "); builder.append(words[i]); } for (int i = builder.length(); i < L; i++) { builder.append(" "); } } else { // middle justified int spaces = (L  count) / diff; int r = (L  count) % diff; for (int i = index+1; i < last; i++) { for(int k=spaces; k > 0; k) { builder.append(" "); } if(r > 0) { builder.append(" "); r; } builder.append(" "); builder.append(words[i]); } } lines.add(builder.toString()); index = last; } return lines; } }

Thanks for sharing. this is my solution.
public class Solution { public List<String> fullJustify(String[] words, int maxWidth) { List<String> res = new ArrayList<String>(); char[] spaces = new char[maxWidth]; for (int i = 0; i < maxWidth; i++){ spaces[i] = ' '; } for (int start = 0; start < words.length;){ int len = words[start].length(); int end = start + 1; for (; end < words.length && len + 1 + words[end].length() <= maxWidth; end++){ len += 1 + words[end].length(); } StringBuilder newStr = new StringBuilder(maxWidth); newStr.append(words[start]); int slotNum = end  start  1; start++; if (end != words.length && slotNum != 0){ int evenNum = (maxWidth  (len  slotNum)) / slotNum; int leftNum = (maxWidth  (len  slotNum)) % slotNum; while (start < end){ newStr.append(spaces, 0, evenNum); if (leftNum > 0){ newStr.append(' '); leftNum; } newStr.append(words[start]); start++; } } else { while (start < end){ newStr.append(' '); newStr.append(words[start]); start++; } newStr.append(spaces, 0, maxWidth  newStr.length()); } res.add(newStr.toString()); } return res; } }

@kg21mn said in Simple Java Solution:
I just cleaned up the solution. It was getting a bit tricky in the original post when it was middle justified.
Much easier to understand than OP's solution

@ayushigarg1992 According to the requirement in problem "If the number of spaces on a line do not divide evenly between words, the empty slots on the left will be assigned more spaces than the slots on the right.", you need to use the extra spaces r on the left side first.
(iindex) is the number of gaps between words. when (iindex) < r, we used one extra space so j <= spaces+1. when (iindex) >= r, the extra space has been used up so j <= spaces.
Here spaces is the total number of empty space divided by the number of gaps between words with even distribution.
spaces = (Lcount)/diff
r is the extra space left after the even distribution.
r = (Lcount)%diffI hope I have made it clear.
@ayushigarg1992 said in Simple Java Solution:
if (i < last  1) for (int j = 0; j <= (spaces + ((i  index) < r ? 1 : 0)); j++) { builder.append(" "); }
What is the logic behind the termination condition here?

@kg21mn Hi, in the middle justification, what do the spaces and r variable signify? Thanks you!

@kg21mn said in Simple Java Solution:
builder.append(" ");
Thanks for sharing, but why still
builder.append(" ");
after you add spaces and reminder spaces after the previous word?