#include <iostream>
#include <string>
#include <vector>

using namespace std;

vector<string> fullJustify(vector<string>& words, int maxWidth) {
    vector<string> ret;
    int start_word = 0, end_word = 0;
    int num_words = end_word - start_word + 1;
    int length_of_words = words[0].size();
    int space_needed = length_of_words + (num_words - 1);

    for (int i=0; i<words.size(); ++i) {
        int next_word_len = 0;
        if (i+1 < words.size())
            next_word_len = words[i+1].size();
        if (i==words.size()-1 || (num_words==1 && (space_needed+next_word_len+1>maxWidth))) {
            //last line or just one word on this line, so left justify
            int count_chars = 0;
            string line;
            for (int j = start_word; j<=end_word; ++j) {
                line += words[j];
                if (line.size() < maxWidth)
                    line += ' ';
            }
            int spaces = maxWidth - line.size();
            for (int j=0; j<spaces; ++j)
                line += ' ';
            ret.push_back(line);
            start_word = i+1;
        }
        else if (num_words>1 && (space_needed+next_word_len+1>maxWidth)) {
            //output multi word line, so spread align centre
            int words_length = 0;
            for (int j=start_word; j<=end_word; ++j)
                words_length += words[j].size();
            int space_breaks = num_words-1;
            int space_chars = maxWidth - words_length;
            int chars_per_space = space_chars / space_breaks;
            string line;
            for (int j=start_word; j<=end_word; ++j) {
                line += words[j];
                if (j == end_word)
                    break;
                int spaces = chars_per_space;
                if (chars_per_space * space_breaks < space_chars)
                    spaces++;
                for (int k=0; k<spaces; ++k)
                    line += ' ';
                space_chars -= spaces;
                space_breaks--;
            }
            ret.push_back(line);
            start_word = i+1;
        }
        //increment counter variables
        if (i==words.size()-1)
            break;
        end_word = i+1;
        num_words = end_word - start_word+1;
        length_of_words = 0;
        for (int j=start_word; j<=end_word; ++j)
            length_of_words += words[j].size();
        space_needed = length_of_words + (num_words-1);
    }
    return ret;
}

void printv(vector<string>& v) {
    for (const string& s : v)
        cout << s << "|\n";
    cout << "\n";
}

int main() {
    vector<string> words {"What","must","be","acknowledgment","shall","be"}; //{"Science","is","what","we","understand","well","enough","to","explain","to","a","computer.","Art","is","everything","else","we","do"}; //{"This", "is", "an", "example", "of", "text", "justification."};
    int maxWidth = 16;
    auto out = fullJustify(words, maxWidth);
    printv(out);

    return 0;
}