How can I split a string into a given number of lines?

Question

Here is my question:

Given a string, which is made up of space separated words, how can I split that into N strings of (roughly) even length, only breaking on spaces?

Here is what I've gathered from research:

I started by researching word-wrapping algorithms, because it seems to me that this is basically a word-wrapping problem. However, the majority of what I've found so far (and there is A LOT out there about word wrapping) assumes that the width of the line is a known input, and the number of lines is an output. I want the opposite.

I have found a (very) few questions, such as this that seem to be helpful. However, they are all focused on the problem as one of optimization - e.g. how can I split a sentence into a given number of lines, while minimizing the raggedness of the lines, or the wasted whitespace, or whatever, and do it in linear (or NlogN, or whatever) time. These questions seem mostly to be unanswered, as the optimization part of the problem is relatively "hard".

However, I don't care that much about optimization. As long as the lines are (in most cases) roughly even, I'm fine if the solution doesn't work in every single edge case, or can't be proven to be the least time complexity. I just need a real world solution that can take a string, and a number of lines (greater than 2), and give me back an array of strings that will usually look pretty even.

Here is what I've come up with: I think I have a workable method for the case when N=3. I start by putting the first word on the first line, the last word on the last line, and then iteratively putting another word on the first and last lines, until my total width (measured by the length of the longest line) stops getting shorter. This usually works, but it gets tripped up if your longest words are in the middle of the line, and it doesn't seem very generalizable to more than 3 lines.

var getLongestHeaderLine = function(headerText) {
  //Utility function definitions
  var getLongest = function(arrayOfArrays) {
    return arrayOfArrays.reduce(function(a, b) {
      return a.length > b.length ? a : b;
    });
  };

  var sumOfLengths = function(arrayOfArrays) {
    return arrayOfArrays.reduce(function(a, b) {
      return a + b.length + 1;
    }, 0);
  };

  var getLongestLine = function(lines) {
    return lines.reduce(function(a, b) {
      return sumOfLengths(a) > sumOfLengths(b) ? a : b;
    });
  };

  var getHeaderLength = function(lines) {
    return sumOfLengths(getLongestLine(lines));
  }

  //first, deal with the degenerate cases
  if (!headerText)
    return headerText;

  headerText = headerText.trim();

  var headerWords = headerText.split(" ");

  if (headerWords.length === 1)
    return headerText;

  if (headerWords.length === 2)
    return getLongest(headerWords);

  //If we have more than 2 words in the header,
  //we need to split them into 3 lines
  var firstLine = headerWords.splice(0, 1);
  var lastLine = headerWords.splice(-1, 1);
  var lines = [firstLine, headerWords, lastLine];

  //The header length is the length of the longest
  //line in the header. We will keep iterating
  //until the header length stops getting shorter.
  var headerLength = getHeaderLength(lines);
  var lastHeaderLength = headerLength;
  while (true) {
    //Take the first word from the middle line,
    //and add it to the first line
    firstLine.push(headerWords.shift());
    headerLength = getHeaderLength(lines);
    if (headerLength > lastHeaderLength || headerWords.length === 0) {
      //If we stopped getting shorter, undo
      headerWords.unshift(firstLine.pop());
      break;
    }
    //Take the last word from the middle line,
    //and add it to the last line
    lastHeaderLength = headerLength;
    lastLine.unshift(headerWords.pop());
    headerLength = getHeaderLength(lines);
    if (headerLength > lastHeaderLength || headerWords.length === 0) {
      //If we stopped getting shorter, undo
      headerWords.push(lastLine.shift());
      break;
    }
    lastHeaderLength = headerLength;
  }

  return getLongestLine(lines).join(" ");
};

debugger;
var header = "an apple a day keeps the doctor away";

var longestHeaderLine = getLongestHeaderLine(header);
debugger;

EDIT: I tagged javascript, because ultimately I would like a solution I can implement in that language. It's not super critical to the problem though, and I would take any solution that works.

EDIT#2: While performance is not what I'm most concerned about here, I do need to be able to perform whatever solution I come up with ~100-200 times, on strings that can be up to ~250 characters long. This would be done during a page load, so it needs to not take forever. For example, I've found that trying to offload this problem to the rendering engine by putting each string into a DIV and playing with the dimensions doesn't work, since it (seems to be) incredibly expensive to measure rendered elements.

Answer 1

Try this. For any reasonable N, it should do the job:

function format(srcString, lines) {
  var target = "";
  var  arr =  srcString.split(" ");
  var c = 0;
  var MAX = Math.ceil(srcString.length / lines);
  for (var i = 0, len = arr.length; i < len; i++) {
     var cur = arr[i];
     if(c + cur.length > MAX) {
        target += '\n' + cur;
     c = cur.length;
     }
     else {
       if(target.length > 0)
         target += " ";
       target += cur;
       c += cur.length;
     }       
   }
  return target;
}

alert(format("this is a very very very very " +
             "long and convoluted way of creating " +
             "a very very very long string",7));

Answer 2

You may want to give this solution a try, using canvas. It will need optimization and is only a quick shot, but I think canvas might be a good idea as you can calculate real widths. You can also adjust the font to the really used one, and so on. Important to note: This won't be the most performant way of doing things. It will create a lot of canvases.

DEMO

var t = `However, I don't care that much about optimization. As long as the lines are (in most cases) roughly even, I'm fine if the solution doesn't work in every single edge case, or can't be proven to be the least time complexity. I just need a real world solution that can take a string, and a number of lines (greater than 2), and give me back an array of strings that will usually look pretty even.`;


function getTextTotalWidth(text) {
    var canvas = document.createElement("canvas");
    var ctx = canvas.getContext("2d");
  ctx.font = "12px Arial";
    ctx.fillText(text,0,12);
  return ctx.measureText(text).width;
}

function getLineWidth(lines, totalWidth) {
    return totalWidth / lines ;
}

function getAverageLetterSize(text) {
    var t = text.replace(/\s/g, "").split("");
  var sum = t.map(function(d) { 
    return getTextTotalWidth(d); 
  }).reduce(function(a, b) { return a + b; });
    return  sum / t.length;
}

function getLines(text, numberOfLines) {
    var lineWidth = getLineWidth(numberOfLines, getTextTotalWidth(text));
  var letterWidth = getAverageLetterSize(text);
  var t = text.split("");
  return createLines(t, letterWidth, lineWidth);
}

function createLines(t, letterWidth, lineWidth) {
    var i = 0;
  var res = t.map(function(d) {
    if (i < lineWidth || d != " ") {
        i+=letterWidth;
        return d;
    }
    i = 0;
    return "<br />";
  })
  return res.join("");
}

var div = document.createElement("div");
div.innerHTML = getLines(t, 7);
document.body.appendChild(div);

Answer 3

(Adapted from here, How to partition an array of integers in a way that minimizes the maximum of the sum of each partition?)

If we consider the word lengths as a list of numbers, we can binary search the partition.

Our max length ranges from 0 to sum (word-length list) + (num words - 1), meaning the spaces. mid = (range / 2). We check if mid can be achieved by partitioning into N sets in O(m) time: traverse the list, adding (word_length + 1) to the current part while the current sum is less than or equal to mid. When the sum passes mid, start a new part. If the result includes N or less parts, mid is achievable.

If mid can be achieved, try a lower range; otherwise, a higher range. The time complexity is O(m log num_chars). (You'll also have to consider how deleting a space per part, meaning where the line break would go, features into the calculation.)

JavaScript code (adapted from http://articles.leetcode.com/the-painters-partition-problem-part-ii):

function getK(arr,maxLength) {
  var total = 0,
      k = 1;

  for (var i=0; i<arr.length; i++) {
    total += arr[i] + 1;

    if (total > maxLength) {
      total = arr[i];
      k++;
    }
  }

  return k;
}
 

function partition(arr,n) {
  var lo = Math.max(...arr),
      hi = arr.reduce((a,b) => a + b); 

  while (lo < hi) {
    var mid = lo + ((hi - lo) >> 1);

    var k = getK(arr,mid);

    if (k <= n){
      hi = mid;

    } else{
      lo = mid + 1;
    }
  }

  return lo;
}

var s = "this is a very very very very "
      + "long and convoluted way of creating "
      + "a very very very long string",
    n = 7;

var words = s.split(/\s+/),
    maxLength = partition(words.map(x => x.length),7);

console.log('max sentence length: ' + maxLength);
console.log(words.length + ' words');
console.log(n + ' lines')
console.log('')

var i = 0;

for (var j=0; j<n; j++){
  var str = '';
  
  while (true){
    if (!words[i] || str.length + words[i].length > maxLength){
      break
    }
    str += words[i++] + ' ';
  }
  console.log(str);
}

Answer 4

I'm sorry this is C#. I had created my project already when you updated your post with the Javascript tag.

Since you said all you care about is roughly the same line length... I came up with this. Sorry for the simplistic approach.

    private void DoIt() {

        List<string> listofwords = txtbx_Input.Text.Split(' ').ToList();
        int totalcharcount = 0;
        int neededLineCount = int.Parse(txtbx_LineCount.Text);

        foreach (string word in listofwords)
        {
            totalcharcount = totalcharcount + word.Count(char.IsLetter);
        }

        int averagecharcountneededperline = totalcharcount / neededLineCount;
        List<string> output = new List<string>();
        int positionsneeded = 0;

        while (output.Count < neededLineCount)
        {
            string tempstr = string.Empty;
            while (positionsneeded < listofwords.Count)
            {
                tempstr += " " + listofwords[positionsneeded];
                if ((positionsneeded != listofwords.Count - 1) && (tempstr.Count(char.IsLetter) + listofwords[positionsneeded + 1].Count(char.IsLetter) > averagecharcountneededperline))//if (this is not the last word) and (we are going to bust the average)
                {
                    if (output.Count + 1 == neededLineCount)//if we are writting the last line
                    {
                        //who cares about exceeding.
                    }
                    else
                    {
                        //we're going to exceed the allowed average, gotta force this loop to stop
                        positionsneeded++;//dont forget!
                        break;
                    }
                }
                positionsneeded++;//increment the needed position by one
            }

            output.Add(tempstr);//store the string in our list of string to output
        }

        //display the line on the screen
        foreach (string lineoftext in output)
        {
            txtbx_Output.AppendText(lineoftext + Environment.NewLine);
        }

    }

Answer 5

Using the Java String Split() Method to split a string we will discover How and Where to Apply This String Manipulation Technique:

We'll examine the Java Split() method's explanation and discover how to apply it. The principles are explained simply and with enough programming examples, either as a separate explanation or in the comment part of the programs.

The Java String Split() method is used to divide or split the calling Java String into pieces and return the Array, as the name implies. The delimiters("", " ", ) or regular expressions that we have supplied separately for each component or item of an array.

Syntax

String[ ] split(String regExp)

First Case: It involves initializing a Java String variable with a variety of words separated by spaces, using the Java String Split() method, and evaluating the results. We can effectively print each word without the space using the Java Split() function.

Second Case: In this case, we initialize a Java String variable and attempt to split or deconstruct the main String variable to use the String Split() method utilizing a substring of the initialized String variable.

Third Case: In this case, we will attempt to split a String using its character by taking a String variable (a single word).

You can check out other approaches to this problem on YouTube and even coding websites on google such as Coding Ninjas

Answer 6

This old question was revived by a recent answer, and I think I have a simpler technique than the answers so far:

const evenSplit = (text = '', lines = 1) => {
  if (lines < 2) {return [text]}
  const baseIndex = Math .round (text .length / lines)
  const before = text .slice (0, baseIndex) .lastIndexOf (' ')
  const after = text .slice (baseIndex) .indexOf (' ') + baseIndex
  const index = after - baseIndex < baseIndex - before ? after : before
  return [
    text .slice (0, index), 
    ... evenSplit (text .slice (index + (before > -1 ? 1 : 0)), lines - 1)
  ]
}

const text = `However, I don't care that much about optimization. As long as the lines are (in most cases) roughly even, I'm fine if the solution doesn't work in every single edge case, or can't be proven to be the least time complexity. I just need a real world solution that can take a string, and a number of lines (greater than 2), and give me back an array of strings that will usually look pretty even.`

const display = (lines) => console .log (lines .join ('\n'))

display (evenSplit (text, 7))
display (evenSplit (text, 5))
display (evenSplit (text, 12))
display (evenSplit (`this should be three lines, but it has a loooooooooooooooooooooooooooooooong word`, 3))

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

It works by finding the first line then recurring on the remaining text with one fewer lines. The recursion bottoms out when we have a single line. To calculate the first line, we take an initial target index which is just an equal share of the string based on its length and the number of lines. We then check to find the closest space to that index, and split the string there.

It does no optimization, and could certainly be occasionally misled by long words, but mostly it just seems to work.