How to efficiently find the ideal column count for strings of a certain width?

Question

I have n strings of different length s₁, s₂, …, s_n that I want to display on a terminal in c columns. The terminal has a width of m characters. Each column i has a certain width w_i which is equal to the width of the longest entry in that column. Between each pair of columns there is a certain amount of space s. The total width of all columns including the space between cannot be larger than the width of the terminal (w₁ + w₂ + … + w_c + (c - 1) · s ≤ m). Each column shall contain ⌈n / c⌉ strings, except when n is not evenly dividable by c, in which case the last few columns shall be shorter by one entry or only the last column shall either be shorter depending on whether the strings are arranged across or down.

Is there an efficient (e.g. O(n·w) where w = max(w₁, w₂, …, w_n)) algorithm to figure out the maximal amount of columns that I can fit into c columns, if...

• the strings are arranged across

  string1 string2  string3 string4
  string5 string6  string7 string8
  string9 string10
  

• the strings are arranged down

  string1 string4 string7 string10
  string2 string5 string8
  string3 string6 string9
  

?

Later findings

I found out that s doesn't matter. Each instance of the problem where s > 0 can be translated into an instance where s = 0 by expanding each string by s characters and also expanding the width of the terminal by s characters to compensate for the extra s characters at the end of the screen.

Answer 1

Unfortunately I think the fastest algorithm you can have is O(n^2). This is because you can determine if a configuration is possible for c columns in a single pass of the list but you can't know by how much to change c so basically you'll just have to try a different value for it. At most your algorithm will do this n times.

This is pseudo-code for how I would do it

for c = n.size, c > 0, c --
  remainingDist = m - c*s
  for i = 1, i <= c, i ++ 
    columnWidth = 0
    for j = i, j <= n.size; j += c
      columnWidth = max(n[j], columnWidth)
    end
    remainingDist -= columnWidth
  end
  if remainingDist >= 0
    success
    columns = c
    break
  end
end

you could jump to midway through the loop by first computing an average size of the items and figure an "ideal" number of columns from that.