daily coding problem #28: Given a sequence of words and an integer line length k, return a list of strings which represents each line, fully justified

readme.md

Good morning! Here's your coding interview problem for today.

This problem was asked by Palantir.

Write an algorithm to justify text. Given a sequence of words and an integer line length k, return a list of strings which represents each line, fully justified.

More specifically, you should have as many words as possible in each line. There should be at least one space between each word. Pad extra spaces when necessary so that each line has exactly length k. Spaces should be distributed as equally as possible, with the extra spaces, if any, distributed starting from the left.

If you can only fit one word on a line, then you should pad the right-hand side with spaces.

Each word is guaranteed not to be longer than k.

For example, given the list of words ["the", "quick", "brown", "fox", "jumps", "over", "the", "lazy", "dog"] and k = 16, you should return the following:

["the  quick brown", # 1 extra space on the left
"fox  jumps  over", # 2 extra spaces distributed evenly
"the   lazy   dog"] # 4 extra spaces distributed evenly

Thought process

• break the problem down so that the word list results in something like this:

[
  [the, quick, brown],
  [fox, jumps, over],
  [the, lazy, dog]
]

• for each fragment, iterate through the number of spaces required to fulfill k. For example, the spaces array would be:

[
  [2, 1], // 2 spaces between 1st and 2nd word, 1 space between 2nd and 3rd word
  [2, 2], // 2 spaces between 1st and 2nd word, 2 spaces between 2nd and 3rd word
  [3, 3]  // 3 spaces between 1st and 2nd word, 3 spaces between 2nd and 3rd word
]

• Finally, stitch the word list and the space list together

Code

const example = [
  "the",
  "quick",
  "brown",
  "fox",
  "jumps",
  "over",
  "the",
  "lazy",
  "dog"
];
const k = 16;

function lengthOfWords(words) {
  return words.reduce((count, word) => {
    count += word.length;
    return count;
  }, 0);
}

let wordList = [];
let sentence = [];
let final = [];

function formatText(words, k) {
  words.forEach((word, index) => {
    //edge case
    // if (word.length >= k - 1 && wordList.length == 0) {
    //   console.log('here')
    //   sentence.push(word)
    //   return
    // }

    if (wordList.length == 0) {
      wordList.push(word);
    } else {
      const spacesBetweenWords = wordList.length - 1;
      if (lengthOfWords(wordList) + spacesBetweenWords + word.length >= k) {
        sentence.push(wordList);
        wordList = [];
      }

      wordList.push(word);

      if (index >= words.length - 1) {
        sentence.push(wordList);
        wordList = [];
      }
    }
  });

  // console.log(wordList)
  // console.log(sentence)

  sentence.forEach(fragment => {
    const spacesNeededInFragment = k - lengthOfWords(fragment);

    // console.log(spacesNeededInFragment)

    let spaces = [];
    if (fragment.length == 1) {
      spaces.push(spacesNeededInFragment);
    } else {
      spaces = new Array(fragment.length - 1).fill(0);

      let q = 0;
      for (let i = 0; i < spacesNeededInFragment; i++) {
        spaces[q] += 1;
        if (q >= spaces.length - 1) {
          q = 0;
        } else {
          q++;
        }
      }
    }

    // console.log(spaces)

    //now string them together

    let part = [];

    fragment.forEach((word, index) => {
      if (fragment.length == 1) {
        part.push(" ".repeat(spaces[index]) + word);
        return;
      }

      if (spaces[index]) {
        part.push(word + " ".repeat(spaces[index]));
      } else {
        part.push(word);
      }
    });

    final.push(part);
  });

  // console.log(sentence)

  final.forEach((fragment, index) => {
    final[index] = fragment.join("");
  });

  return final;
}

const result = formatText(example, 16);

console.log(result);

/*
[ 'the  quick brown', 'fox  jumps  over', 'the   lazy   dog' ]
*/