LeetCode Entry

68. Text Justification

24.08.2023 hard 2023 kotlin

Spread words to lines, evenly spacing left->right, and left-spacing the last line

68. Text Justification hard blog post substack

image.png

Join me on Telegram

https://t.me/leetcode_daily_unstoppable/318

Problem TLDR

Spread words to lines, evenly spacing left->right, and left-spacing the last line

Intuition

Scan word by word, checking maxWidth overflow.

Approach

Separate word letters count and count of spaces. To spread spaces left-evenly, iteratively add spaces one-by-one until maxWidth reached. Using Kotlin built-in functions helps to reduce boilerplate:

  • buildList
  • buildString
  • padEnd

Complexity

  • Time complexity: \(O(wn)\)

  • Space complexity: \(O(wn)\)

Code


    fun fullJustify(words: Array<String>, maxWidth: Int) = buildList<String> {
      val line = mutableListOf<String>()
      fun justifyLeft() = line.joinToString(" ").padEnd(maxWidth, ' ')
      var wLen = 0
      fun justifyFull() = buildString {
        val sp = IntArray(line.size - 1) { 1 }
        var i = 0
        var len = wLen + line.size - 1
        while (len++ < maxWidth && line.size > 1) sp[i++ % sp.size]++
        line.forEachIndexed { i, w ->
          append(w)
          if (i < sp.size) append(" ".repeat(sp[i]))
        }
      }
      words.forEachIndexed { i, w ->
        if (wLen + line.size + w.length > maxWidth) {
          add(if (line.size > 1) justifyFull() else justifyLeft())

          line.clear()
          wLen = 0
        }
        line += w
        wLen += w.length
      }
      add(justifyLeft())
    }