Say you are given two sentences with a line in the middle (denoted by \'|\'):\n```\n\na cat ran across the    |I like to sing and \nstreet                  |dance the night\n                        |away\n```\n\nThe only thing you have control over is moving the middle line, while the total length of each line is fixed. Design an algorithm to figure out how where to place the middle line such that you ensure that the two sentences take up the least amount of lines.\n\nFor example, the answer would be making the line such that it\'s like this:\n\n```\n\na cat ran across the |I like to sing and dance\nstreet               | the night away\n```\n\nShifting the line all the way to the left would result in:\n\n```\n\na  |I like to sing and dance the night away\ncat|\nran|\n...|\n...|\n```\n\nBasically, in this example, the most you can shift to the left is dependent on the length of the longest word in the "left" sentence.\n\nInterviewer was looking for an answer better than O(N^2) runtime (I\'m guessing O(N)) with some sort of DP solution. Couldn\'t crack it.

Say you are given two sentences with a line in the middle (denoted by \'|\'):\n\n\na cat ran across the    |I like to sing and \nstreet                  |dance 