How can I evenly balance a string over the minimum amount of lines using only JavaScript?

Question

I'm trying to evenly balance text over multiple lines using only JavaScript and without caring about the complexity of font sizes.

Given an input string and the maximum¹ amount of characters in each line, how can I evenly balance² the text over the minimum amount of lines?

I'm using an up-to-date version of Google Chrome and legacy browser support isn't important to my question.

Below is my attempt without trying to balance the text (which I want but I don't know how to go about doing it).

It might be possible to remove one or both of the replace() methods by changing the RegExp's string in the match() method.

const stringInputsAndExpectedArrayOutputs = [
  ['', ['']],
  [' ', ['']],
  ['  ', ['']],
  ['.', ['.']],
  ['The ', ['The']],
  ['The quick\nbrown fox', ['The quick brown', 'fox']],
  ['Thequickbrownfox jumpsoverthelazydog.', ['Thequickbrownfox', 'jumpsoverthelazydog.']],
  ['   The   quick   brown   fox   jumps   over   the   lazy   dog.   ', ['The quick brown', 'fox jumps over', 'the lazy dog.']],
  ['The quick brown fox jumps over the lazy dog.', ['The quick brown', 'fox jumps over', 'the lazy dog.']]
];
const maximumCharactersPerLine = 15;

const distributeTextOverLines = ((stringInput, maximumCharactersPerLine) => {
  let arrayOutput = stringInput.replace(/[\r\n ]+$/g, '').replace(/[\r\n ]{2,}|[\r\n]/g, ' ');
  arrayOutput = arrayOutput.match(new RegExp(`(?! )(?:.{1,${maximumCharactersPerLine}}|[^ ]+)(?= |$)`, 'g')) || [''];
  return arrayOutput;
});

for (const [stringInput, expectedArrayOutput] of stringInputsAndExpectedArrayOutputs) {
  const arrayOutput = distributeTextOverLines(stringInput, maximumCharactersPerLine);
  const arrayOutputDifferentThanExpected = !(arrayOutput.length === expectedArrayOutput.length && arrayOutput.every((value, index) => value === expectedArrayOutput[index]));
  if (arrayOutputDifferentThanExpected) {
    console.log('array output:');
    console.log(arrayOutput);
    console.log('expected array output:');
    console.log(expectedArrayOutput);
    continue;
  }
  const stringOutput = arrayOutput.join('\n');
  console.log('string output:');
  console.log(stringOutput);
}

.as-console-wrapper {
  max-height: 100% !important;
  top: 0;
}

---

¹ If a word is longer than the maximum limit then the line must contain the whole word overflowing it.
² Distribute the text in a way so that each line has as similar amount of characters as the other ones have as possible which makes the width of all the lines together as small as possible.

Answer 1

For the even distribution, I would suggest a binary search algorithm:

1. Do a greedy distribution, like you already did. This fixes the number of lines that the solution must have.
2. Calculate a theoretical minimum width, based on the total number of characters, the maximum width and the number of lines you have at your disposition.
3. Perform a binary search in the range between these two width extremes to find the smallest width for which the (greedy) distribution can still fit in that number of lines.

Here is an interactive snippet that allows you to provide text and the maximum width. The output is generated with every change you make.

Just for convenience, the output starts with an extra line of hyphens, filling up the given maximum width. That way you can better visualise how much the result below it deviates from the input width.

function breakLines(text, maxWidth) {
    function greedy(wordSizes, maxWidth) {
        let width = 0;
        let lineWidth = maxWidth;
        let firstWordPerLine = [];
        wordSizes.forEach((wordSize, i) => {
            if (lineWidth + wordSize >= maxWidth) {
                firstWordPerLine.push(i);
                lineWidth = wordSize;
            } else {
                lineWidth += 1 + wordSize;
            }
            if (lineWidth > width) width = lineWidth;
        });
        
        return { firstWordPerLine, width }
    }
    
    let words = text.match(/\S+/g);
    if (!words) return "";
    let wordSizes = words.map(word => word.length);
    let letterCount = wordSizes.reduce((a, b) => a+b);
    
    // Perform a greedy distribution
    let { firstWordPerLine, width } = greedy(wordSizes, maxWidth);
    let bestLines = firstWordPerLine;
    if (width <= maxWidth) { // There is not a word that causes overflow:
        let minWidth = Math.ceil((letterCount + words.length) / bestLines.length) - 1;
        // Perform binary search for optimal width
        while (minWidth < maxWidth) {
            let mid = (minWidth + maxWidth) >> 1;
            let { firstWordPerLine, width } = greedy(wordSizes, mid);
            if (firstWordPerLine.length > bestLines.length) {
                minWidth = mid + 1;
            } else if (width > mid) {
                bestLines = firstWordPerLine;
                break;
            } else {
                maxWidth = width;
                bestLines = firstWordPerLine;
            }
        }
    }
    // Convert bestLines & words to output
    let output = [];
    while (bestLines.length) {
        output.push(words.splice(bestLines.pop(), Infinity).join(" "))
    }
    return output.reverse().join("\n");
    
}

// I/O handling
let widthInput = document.querySelector("#maxwidth");
let inputText = document.querySelector("#text");
let outputText = document.querySelector("#aligned");

document.addEventListener("input", refresh);

function refresh() {
    let text = inputText.value;
    let maxWidth = Math.min(text.length, Math.max(0, +widthInput.value || 0));
    text = breakLines(text, maxWidth);
    outputText.textContent = "-".repeat(maxWidth) + "\n" + text;
}
refresh();

#maxwidth { width: 5em; }
#text { width: 100%; height: 5em }
#aligned { border: 0.5px solid; width:min-content }

max width: <input type="number" id="maxwidth" value="50" min="0"><br>
Input: <br>
<textarea id="text">Lorem ipsum dolor sit amet, consectetur adipiscing elit, sed do eiusmod tempor incididunt ut labore et dolore magna aliqua. Ut enim ad minim veniam, quis nostrud exercitation ullamco laboris nisi ut aliquip ex ea commodo consequat. Duis aute irure dolor in reprehenderit in voluptate velit esse cillum dolore eu fugiat nulla pariatur. Excepteur sint occaecat cupidatat non proident, sunt in culpa qui officia deserunt mollit anim id est laborum.</textarea><br>

Output:
<pre id="aligned"></pre>

(Open the snippet in full page mode for a better experience)