1
class Solution {
2
  string preprocessing(string &f, int space, int limit) {
3
    int noofspace = limit - f.size() + space;
4
    int k = 0;
5
    string r = "";
6
    while (space) {
7
      int n = noofspace / space;
8
      if ((noofspace % space) != 0) n += 1;
9
      noofspace -= n;
10
      while (f[k] != ' ') {
11
        r += f[k];
12
        k++;
13
      }
14
      k++;
15
      while (n--) {
16
        r += ' ';
17
      }
18
      space--;
19
    }
20
    while (k < f.size()) {
21
      r += f[k];
22
      k++;
23
    }
24
    while (noofspace--) r += ' ';
25
    return r;
26
  }
27

28
 public:
29
  vector<string> fullJustify(vector<string> &words, int maxWidth) {
30
    vector<string> ans;
31
    string f = "";
32
    int space = 0;
33
    for (string &str : words) {
34
      if ((f.size() + str.size() + 1) <= maxWidth && f.size() > 0) {
35
        f += ' ' + str;
36
        space++;
37
      } else {
38
        if (f.size() > 0) {
39
          f = preprocessing(f, space, maxWidth);
40
          ans.push_back(f);
41
          f = "";
42
        }
43
        f += str;
44
        space = 0;
45
      }
46
    }
47
    int sz = f.size();
48
    while (sz < maxWidth) {
49
      f += ' ';
50
      sz++;
51
    }
52
    ans.push_back(f);
53
    return ans;
54
  }
55
};