# Calculate the target size to truncate to fit strings inside a specific size

## The problem

I'm writing a program to display tags (strings) in the console, and I need to fit them inside a specific width. I need to truncate the some tags when their total length is too large. I'm looking for an efficient algorithm to calculate the maximum size for all strings to truncate to.

For example, assume that we have 3 tags to display, and the total available size is 12 characters. The following code block shows how to fit them inside the available space. (In the real situation we also need separators between them, but for simplicity they are omitted here.)

``````The tags:
11111         5 chars wide
2222222       7 chars
333           3 chars

The space:
|------------| 12 chars

Not truncated:
111112222222333   5+7+3 = 15 chars, too long

Truncate every tag to 4 chars:
11112222333   4+4+3 = 11 chars, fits
``````

Similarly, if the space is 13 characters long, the trucated size is 5 chars:

``````|-------------|
1111122222333  5+5+3 = 13 chars, fits
``````

## My current solution

I currently use a trivial way to solve this problem. Here's the pseudocode:

``````// the input
tags = [...]
target_width = ...

tag_widths = tags.map(x => x.width).sort()
total_width = tag_width.sum()

truncated_count = 0
truncate_to = tag_widths[0]

// list of items
// v      | <- truncation line
// *******|
// *****  |
// ***    |

while true {
// find the next group of tags with the same length
//
//      |
// ******* <-
// *****|
// ***  |
truncated_count += 1
while truncated_count < tags.length
&& tag_widths[truncated_count] == truncate_to {
truncated_count += 1
}
// new_truncate_to is the width of the next group
new_truncate_to = tag_widths[truncated_count] or 0 if truncated_count > tags.length

// calculate the length after truncating all of them
//
//      |
// *****|--
// *****|
// ***  |
new_total_width = total_width - truncated_count * (new_truncate_to - truncate_to)

if new_total_width <= target_width {
// the target length is between truncate_to and new_truncate_to
//       |
// ******|-
// ***** |
// ***   |
new_truncate_to += floor((target_width - new_total_width) / truncated_count)
truncate_to = new_truncate_to
break
} else {
// the current truncation is not enough
total_width = new_total_width
truncate_to = new_truncate_to
}
}

// the result
truncate_to
``````

Is there any algorithm that is more efficient?

I cannot fully understand your code, but I propose a slightly more efficient algorithm.

The most of the cost is the initial sorting of the widths O(n*log n), then the rest is done with a single pass on the array.

Pseudo-code:

``````let remainingwidth = total available width
sort tags array by width
for i=0, i<tags.length; i=i+1
let avg_avail_width = remainingwidth / (tags-length - i)  //Integer division, rounded down
if tags[i].width > avg_avail_width
tags[i].width = avg_avail_width
end if
remainingwidth -= tags[i].width
end for each
``````

Note that in case the available width cannot be distributed evenly (e.g. total width 20, tag widths [3,7,8,9], 20-3 = 17 so we cannot have equal widths for the remaining tags) this strategy assign the extra space to the tags with the longest original widths.