68. Text Justification

class Solution {
public:
    vector<string> fullJustify(vector<string>& words, int maxWidth)
    {
        int n = words.size();
        int start = 0;
        vector<string> res;
        while (start < n)
        {
            int last = start, totalChars = 0;
            while (last < n && totalChars + words[last].size() + last - start <= maxWidth)
            {
                totalChars += words[last++].size();
            }

            string cur;

            int space = maxWidth - totalChars;

            for (int k = start; k < last; ++k)
            {
                cur += words[k];
                if (space > 0)
                {
                    int cnt;

                    if (last == n)
                    {
                        if (last - k == 1)
                        {
                            cnt = space;
                        }
                        else
                        {
                            cnt = 1;
                        }
                    }
                    else
                    {
                        if (last - k > 1)
                        {
                            if (space % (last - k - 1) == 0)
                            {
                                cnt = space / (last - k - 1);
                            }
                            else
                            {
                                cnt = space / (last - k - 1) + 1;
                            }
                        }
                        else
                        {
                            cnt = space;
                        }
                    }
                    cur.append(cnt, ' ');
                    space -= cnt;
                }
            }
            res.push_back(cur);
            start = last;
        }
        return res;
    }
};

• T: $O(N \cdot K)$
• S: $O(M)$