Optimising String split into chunks of fixed size

Question

I am looking to optimise my solution of the 'SMS problem', i.e splitting a String into chunks of the same size without splitting words.

I did a recursion and am looking for ways to optimise that code, or a more efficient algorithm. In my solution spaces are left at the beginning of each chunk, this is voluntary.

Here is the code:

var exampleTxt = `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.`;

function getIndexOfLastSpace(msg, nthChar) {  
  var curMsg = msg.substring(0, nthChar);
  console.log(curMsg.lastIndexOf(" "));
  return curMsg.lastIndexOf(" ");
}

function getMessagesNumber (msg) {

  if (msg.length < 1) {
    return 0;
  } else if (msg.length > 1 & msg.length < 153) {
    return 1;
  } else {

    var messages = [];

    while (msg.length > 0) {
      var chunk;
      // Last message      
      if (msg.length <= 153) {      
        chunk = msg;
      } else {
        var lastSpaceIndex = getIndexOfLastSpace(msg, 153);        
        chunk = msg.substring(0, lastSpaceIndex);
      }
      messages.push(chunk);
      msg = msg.replace(chunk, '');
    }
    return messages.length;
  }
}

console.log(getMessagesNumber(exampleTxt));

Also am I write in thinking that the complexity of this algorithm is O(n) ?

Answer 1

Firstly, great implementation. Getting the maximum amount of characters for the next chunk, finding the last space in that and then using it to get the correct chunk is fast and works well. Other ideas that spring to mind would be to split the string into words first and rebuild with a loop, but I think this would be slower.

Yes this is O(n) - the solution's speed is proportional to the amount of input passed.

Your solution is a loop, not a recursion. A recursive solution would be a function which calls itself. If you want to see this style, let me know and I can post it.

Some improvements:

• You don't need to wrap the exampleTxt variable in backticks. This creates a template literal, which is unnecessary here - you can just use normal quotes.
• Running the function with a 1 character string causes it to run the while loop, instead of returning early.
• You can simplify the levels of nesting in the if ... else by returning early. If one of the returns is triggered then nothing after it will be run.

if (msg.length < 1) {
    return 0;
}

if (msg.length >= 1 & msg.length < 153) {
    return 1;
}

// while loop

return messages.length;

• In the else if you have & (Bitwise AND) instead of && (Logical AND).
• Your while loop mutates the state of the msg variable. Mutation can lead to hard to find bugs - clone the string first (remainingMsg = msg) and use that in the loop instead.
• It's not necessary to have the getIndexOfLastSpace function separate. You can use something like this:

var nextChunk = msg.substring(0, 153);
nextChunk = nextChunk.substring(0, nextChunk.lastIndexOf(' '));

• To make the function more reusable you could return the message chunks directly instead of the length. The user can then call .length on the returned value if that's all they want.
• You could also pass the chunk length into the function as a parameter, so that it can handle chunking to any length.
• If using the point above, setting some standard values as consts is a good practice.

const SMS_MESSAGE_MAX_LENGTH = 153;
// ...
getMessagesNumber(msg, SMS_MESSAGE_MAX_LENGTH);

• For a higher level abstraction you could use a curryable function to create new functions with specific chunk lengths. I've used ES5 format as that's how the question was asked.

var chunk = function(chunkLength) {
    return (function splitChunks (message) {
        // ...
    });
};

var chunkSmsMessage = chunk(153);
chunkSmsMessage('Lorem ipsum...');