https://leetcode.com/problems/text-justification/

Leetcode: 68. Text Justification

func fullJustify(words []string, maxWidth int) []string {
    // breakup input words into groups that 
    // won't exceed max width once spaces are added
    
    lines := [][]string{}
    lineWords := []string{}
    width := 0
    for _, word := range words {
        // start new line if word cant fit on the current line
        if maxWidth - width - len(lineWords) < len(word) {
            lines = append(lines, lineWords)
            lineWords = []string{}
            width = 0
        }
        
        width += len(word)
        lineWords = append(lineWords, word)
    }
    lines = append(lines, lineWords)
    
    // go through each group of words and format into line of max 
    
    linesFormatted := []string{}
    for i, lineWords := range lines {
        formatted := ""
        // lines with 1 word OR last word are simply left justified
        // all other lines are left+right justified
        
        if i == len(lines)-1 || len(lineWords) == 1 {
            formatted = strings.Join(lineWords, " ")
            formatted += spaces(maxWidth - len(formatted))
        } else {
            // construct the line right-to-left, adding spacing
            // as appropriate to match the desired max length
            // doing this right-to-left ensures that extra spaces are added
            // to the left most slots
            
            for i := len(lineWords)-1; i >= 0; i-- {
                if i == 0 {
                    formatted = lineWords[i] + formatted
                    continue
                }
                numSpaces := numSpacesNeeded(lineWords[:i+1], maxWidth - len(formatted)) / i
                formatted = spaces(numSpaces) + lineWords[i] + formatted
            }
        }
        linesFormatted = append(linesFormatted, formatted)
    }
    return linesFormatted
}

// helper func to give a string of len n consisting of only spaces
func spaces(n int) string {
    s := ""
    for i := 0; i < n; i++ {
        s += " "
    }
    return s
}

// calculates the number of spaces needed to be added 
// between a given group of words to match a desired max length
func numSpacesNeeded(words []string, maxLength int) int {
    total := 0
    for _, word := range words {
        total += len(word)
    }
    return maxLength - total
}