package main

import (
	"strings"
)

func fullJustify(words []string, maxWidth int) (ans []string) {
	beg, width := 0, -1
	for i := range words {
		if width+len(words[i]) >= maxWidth {
			// Arrange words in [beg, i)
			ans = append(ans, arrange(words, beg, i, width, maxWidth))
			// Reset status
			beg, width = i, -1
		}
		width += len(words[i]) + 1
	}
	// Arrange the last group of words,
	// the last line must be left-justified instead of fully-justified.
	prefix := strings.Join(words[beg:], " ")
	trail := strings.Repeat(" ", maxWidth-len(prefix))
	ans = append(ans, prefix+trail)
	return
}

func arrange(words []string, beg, end, width, maxWidth int) string {
	n := end - beg
	space := maxWidth - (width - n + 1)
	if n == 1 {
		return words[beg] + strings.Repeat(" ", space)
	}
	gap, remain := space/(n-1), space%(n-1)
	var sb strings.Builder
	for i := 0; i < n; i++ {
		sb.WriteString(words[beg+i])
		if space > 0 {
			sb.WriteString(strings.Repeat(" ", gap))
			space -= gap
			if i < remain {
				sb.WriteByte(' ')
				space--
			}
		}
	}
	return sb.String()
}

// func main() {
// 	w := []string{"Science", "is", "what", "we", "understand", "well", "enough", "to", "explain",
// 		"to", "a", "computer.", "Art", "is", "everything", "else", "we", "do"}
// 	fmt.Println(fullJustify(w, 20))
// 	w = []string{"What", "must", "be", "acknowledgment", "shall", "be"}
// 	fmt.Println(fullJustify(w, 16))
// }