Text Justification

                                            
class Solution {
public:
    vector<string> fullJustify(vector<string>& words, int maxWidth) {
        vector<string> result;
        int n = words.size();
        int i = 0;
        while (i < n) {
            int j = i, len = 0;
            while (j < n && len + words[j].size() + j - i <= maxWidth) {
                len += words[j].size();
                j++;
            }
            string line = "";
            int diff = maxWidth - len;
            int numGaps = j - i - 1;
            if (j == n || numGaps == 0) {
                for (int k = i; k < j; k++) {
                    line += words[k];
                    if (k < j - 1) line += " ";
                }
                line += string(maxWidth - line.size(), ' ');
            } else {
                int spaces = diff / numGaps;
                int extraSpaces = diff % numGaps;
                for (int k = i; k < j - 1; k++) {
                    line += words[k];
                    line += string(spaces, ' ');
                    if (k - i < extraSpaces) line += " ";
                }
                line += words[j - 1];
            }
            result.push_back(line);
            i = j;
        }
        return result;
    }
};

                                            
class Solution(object):
    def fullJustify(self, words, maxWidth):
        """
        :type words: List[str]
        :type maxWidth: int
        :rtype: List[str]
        """
        result = []
        line = []
        line_length = 0
        for word in words:
            if line_length + len(word) + len(line) > maxWidth:
                for i in range(maxWidth - line_length):
                    line[i % (len(line) - 1 or 1)] += ' '
                result.append(''.join(line))
                line = []
                line_length = 0
            line.append(word)
            line_length += len(word)
        result.append(' '.join(line).ljust(maxWidth))
        return result

                                            
class Solution {
    /**
     * @param String[] $words
     * @param Integer $maxWidth
     * @return String[]
     */
    function fullJustify($words, $maxWidth) {
        $result = [];
        $line = [];
        $lineLength = 0;
        
        foreach ($words as $word) {
            if ($lineLength + count($line) + strlen($word) > $maxWidth) {
                foreach ($line as $i => &$w) {
                    if (count($line) == 1) {
                        $line[$i] .= str_repeat(' ', $maxWidth - $lineLength);
                    } elseif ($i != count($line) - 1) {
                        $spaces = $maxWidth - $lineLength;
                        $line[$i] .= str_repeat(' ', intval($spaces / (count($line) - 1) + ($i < $spaces % (count($line) - 1))));
                    }
                }
                $result[] = implode('', $line);
                $line = [];
                $lineLength = 0;
            }
            
            $line[] = $word;
            $lineLength += strlen($word);
        }
        
        $result[] = implode(' ', $line) . str_repeat(' ', $maxWidth - $lineLength - count($line) + 1);
        
        return $result;
    }
}

                                            
class Solution {
    func fullJustify(_ words: [String], _ maxWidth: Int) -> [String] {
        var result: [String] = []
        var index = 0
        
        while index < words.count {
            var lineWords: [String] = []
            var lineLength = 0
            
            while index < words.count && lineLength + words[index].count + lineWords.count <= maxWidth {
                lineWords.append(words[index])
                lineLength += words[index].count
                index += 1
            }
            
            var line = ""
            
            if index == words.count || lineWords.count == 1 {
                line = lineWords.joined(separator: " ")
                line += String(repeating: " ", count: maxWidth - line.count)
            } else {
                let totalSpaces = maxWidth - lineLength
                let spaceCount = lineWords.count - 1
                var spaces = Array(repeating: totalSpaces / spaceCount, count: spaceCount)
                for i in 0..<totalSpaces % spaceCount {
                    spaces[i] += 1
                }
                
                for (i, word) in lineWords.enumerated() {
                    line += word
                    if i < spaces.count {
                        line += String(repeating: " ", count: spaces[i])
                    }
                }
            }
            
            result.append(line)
        }
        
        return result
    }
}

                                            
class Solution {
    fun fullJustify(words: Array<String>, maxWidth: Int): List<String> {
        val result = mutableListOf<String>()
        var index = 0
        
        while (index < words.size) {
            var line = ""
            var count = 0
            var lineWords = mutableListOf<String>()
            
            while (index < words.size && count + words[index].length + lineWords.size <= maxWidth) {
                lineWords.add(words[index])
                count += words[index].length
                index++
            }
            
            if (index == words.size || lineWords.size == 1) {
                // Left justify for last line or single word line
                line = lineWords.joinToString(" ")
                line += "".padEnd(maxWidth - line.length)
            } else {
                val totalSpaces = maxWidth - count
                val spacesBetweenWords = totalSpaces / (lineWords.size - 1)
                val extraSpaces = totalSpaces % (lineWords.size - 1)
                
                for (i in lineWords.indices) {
                    line += lineWords[i]
                    if (i < lineWords.size - 1) {
                        line += " ".repeat(spacesBetweenWords)
                        if (i < extraSpaces) {
                            line += " "
                        }
                    }
                }
            }
            
            result.add(line)
        }
        
        return result
    }
}

To solve this coding challenge, you need to format a given list of words into a fully justified text where each line has exactly

maxWidth

characters. Each line (except for the last one) should have words separated by spaces as evenly as possible. We'll approach this problem step by step, using a greedy algorithm to pack as many words as possible into each line and then distribute spaces accordingly. Here's how we can achieve it:

# Explanation

Initialization : Start by initializing some variables to keep track of the current line, the current length of the line, and the final result.
Building Lines : Iterate through the words list and keep adding words to the current line until adding another word would exceed
maxWidth

.
Distributing Spaces : When adding another word would exceed
maxWidth

, distribute spaces in the current line to fully justify it:

Calculate the total number of spaces needed.
Distribute the extra spaces evenly between the words.
Handle cases where spaces don't divide evenly by adding extra spaces to the left slots.

Left-Justification for the Last Line : After processing all words, left-justify the last line (since the last line should not be fully justified).
Append to Result : Append each fully justified (or left-justified for the last line) to the final result.

# Detailed Steps in Pseudocode

Initialize Needed Variables :

result_list

: To store the final list of justified lines.
current_line

: To store words of the current line.
current_line_length

: To keep track of the length of the current line.

Iterate Through Words :

For each word in
words

:

Check if adding the new word exceeds
maxWidth

.
If it exceeds, format the current line and reset variables for a new line.
If it does not exceed, add the word to the current line and update the current line length.

Justify the Current Line :

When a new word exceeds the
maxWidth

, you distribute spaces:

Calculate extra spaces required.
Distribute spaces evenly.
Handle extra spaces that don’t divide evenly by adding them to the leftmost slots.

Move the current line to the result list after formatting.

Left-Justify the Last Line :

For the last line, left-justify it by adding spaces only to the end of the current line until
maxWidth

is reached.

Return the Result :

Finally, return the
result_list

.

Pseudocode with Comments

                                            
# Initialize variables
initialize 'result_list' as an empty list
initialize 'current_line' as an empty list
initialize 'current_line_length' as 0

# Iterate through each word
for each word in 'words':
    # Check if adding this word would exceed maxWidth
    if 'current_line_length' + length of 'word' + number of words in 'current_line' > 'maxWidth':
        # We need to distribute spaces to justify 'current_line'
        
        # Calculate total spaces needed
        spaces_needed = 'maxWidth' - 'current_line_length'
        # Initialize space slots
        number_of_gaps = length of 'current_line' - 1 or 1  # to avoid division by zero

        # Distribute spaces
        for i in range(spaces_needed):
            'current_line[i % number_of_gaps]' += ' '  # distribute spaces evenly

        # Join words in 'current_line' and add to result_list
        result_line = ''.join('current_line')
        'result_list'.append(result_line)

        # Reset for the new line
        'current_line' = [word]
        'current_line_length' = length of 'word'
    else:
        # Add the word to the current line
        'current_line'.append('word')
        'current_line_length' += length of 'word'

# Process the last line (left-justified)
result_line = ' '.join('current_line').ljust('maxWidth')
'result_list'.append(result_line)

return 'result_list'

By following these detailed steps and pseudocode, you can fully justify the given text into lines of exactly

maxWidth

characters, ensuring even distribution of spaces between words while handling edge cases like uneven space spread and left-justified last line.