PrettyPrinting_Vlad

package weblab;

import java.util.List;
import java.util.ArrayList;


class Solution {

  static List<String> ans;

  static long[][] precomputSlack(int N, String[] words, int L) {

      long[][] S = new long[N + 1][N + 1];

      for (int i = 1; i <= N; ++i) {
        int l = -1;
        for (int j = i; j <= N; ++j)
          {
            l += (words[j].length() + 1);
            if (l > L)
              S[i][j] = Integer.MAX_VALUE / 2;
            else
              S[i][j] = L - l;
          }
      }

      return S;

  }

  static long[] DP (long[][] S, int N) {
    long[] OPT = new long[N + 1];
    OPT[0] = 0; // Base case
    for (int i = 1; i <= N; ++i) {
      OPT[i] = Integer.MAX_VALUE / 2;
      for (int k = 1; k <= i; ++k)
        OPT[i] = Math.min(OPT[i], S[k][i] * S[k][i] + OPT[k-1]);
    }

    return OPT;
  }

  static void Reconstruct(long[] OPT, String[] words, long[][] S, int i) {
    if (i == 0)
      return;

    StringBuilder sb = new StringBuilder();

    int k = 1;

    while (k <= i)
      if (OPT[i] == S[k][i] * S[k][i] + OPT[k-1])
        {
          Reconstruct(OPT, words, S, k - 1);
          for (int idx = k; idx <= i; ++idx)
          if (i != idx)
            sb.append(words[idx] + " ");
          else
            sb.append(words[idx]);

          ans.add(sb.toString());
          break;
        }
      else k ++;



    return;
  }

    /**
     * @param L the maximum line length
     * @param n the number of words
     * @param words the actual words at indices 1 through n (including).
     * @return
     */
    public static List<String> solve(int L, int N, String[] words) {
        ans = new ArrayList<>();
        long[][] S = precomputSlack(N, words, L);
        // for (int i = 1; i <= N; ++i)
        //   {
        //     for (int j = 1; j <= N; ++j)
        //       System.out.print(S[i][j] + " ");
        //     System.out.println();
        //   }

        long[] OPT = DP(S, N);
        // for (int i = 0; i <= N; ++i)
        // System.out.print(OPT[i] + " ");

        Reconstruct(OPT, words, S, N);

        // System.out.println(ans.size());
        // for (String s: ans)
        //   System.out.println(s);

        return ans;

    }
}