As Eran noted in his answer, you want to split at approximately the line length divided by the desired number of lines, but have to adjust for that being in the middle of a word.
I think his solution won't quite always give the best solution though, as it might sometimes be best to split before the word instead of after as he's doing.
A divide-and-conquer approach would be a recursive algorithm roughly as follows:
Let N be the desired number of lines and LENGTH be the number of characters in the input string (normalizing to single-spaces first).
If the character at LENGTH/N is a space, make the first cut there, and recursively call to split the remainder into N-1 lines, otherwise find the spaces at each end of the word containing this character and make trial cuts at both points with recursive calls again tom complete both cuts. Score the results somehow and choose the better.
I have implemented this as follows. For the scoring function, I chose to minimize the maximum length of lines in the split. A more complex scoring function might possibly improve the results, but this seems to work for all your cases.
public class WordWrapper { public String wrapWords(String input, int lines) { return splitWords(input.replaceAll("\\s+", " "), lines); } private String splitWords(String input, int lines) { if (lines <= 1) { return input; } int splitPointHigh = findSplit(input, lines, 1); String splitHigh = input.substring(0, splitPointHigh).trim() + "\n" + splitWords(input.substring(splitPointHigh).trim(), lines - 1); int splitPointLow = findSplit(input, lines, -1); String splitLow = input.substring(0, splitPointLow).trim() + "\n" + splitWords(input.substring(splitPointLow).trim(), lines - 1); if (maxLineLength(splitLow) < maxLineLength(splitHigh)) return splitLow; else return splitHigh; } private int maxLineLength(String split) { return maxLength(split.split("\n")); } private int maxLength(String[] lines) { int maxLength = 0; for (String line: lines) { if (line.length() > maxLength) maxLength = line.length(); } return maxLength; } private int findSplit(String input, int lines, int dir) { int result = input.length() / lines; while (input.charAt(result) != ' ') result+= dir; return result; } }
I didn't actually bother with the special case of the lucky situation of the simple split landing on a space, and adding special handling for that might make it a little quicker. This code will in that case generate two identical "trial splits" and "choose one".
You might want to make all these methods static of course, and the recursion might give you a stack overflow for large inputs and large line counts.
I make no claim that this is the best algorithm, but it seems to work.
