Maximum Font to Fit a Sentence in a Screen

Medium

Asked by:

1 view

Topics:

Binary Search

You are given a string text. You want to display text on a screen of width width and height height. You can choose any font size from array fonts where each font size is the height of the font. You can choose any font size you want to display text.

You can only use one font size. After that, you will have to decide how many lines you want to display the text. The length of each line must be equal or less than width. You are also given a function cost that determines the cost of each character with a certain font size. cost[i][j] is the cost of character j with font size fonts[i]. You should choose the smallest font size and the minimum number of lines to display text with the lowest cost.

Return the font size you choose to display text with the lowest cost. If there is no way to display text on the screen, return -1.

Note:

You can break lines at any character.
Please remember that the height of the screen is height and the width is width.

Example 1:

Input: text = "abc", width = 5, height = 10, fonts = [1,2,3,4,5], cost = [[1,2,3],[2,3,4],[3,4,5],[4,5,6],[5,6,7]]
Output: 2
Explanation:
The screen looks like this if we choose font size 1:
abc
The screen looks like this if we choose font size 2:
ab
c
The screen looks like this if we choose font size 3:
ab
c
The screen looks like this if we choose font size 4:
ab
c
The screen looks like this if we choose font size 5:
ab
c
We should choose font size 2 because it has the minimum cost.

Example 2:

Input: text = "abc", width = 5, height = 10, fonts = [1,2], cost = [[1,2,3],[2,3,4]]
Output: 1
Explanation:
The screen looks like this if we choose font size 1:
abc
The screen looks like this if we choose font size 2:
ab
c
We can choose font size 1 or font size 2 but font size 1 has the lowest cost.

Example 3:

Input: text = "leetcode", width = 6, height = 5, fonts = [3,4,5,6,7,8,9,10], cost = [[7026,7045,7032,7041,7025,7033,7023,7038],[7039,7042,7030,7047,7042,7036,7044,7032],[7041,7040,7039,7036,7026,7024,7032,7030],[7045,7044,7033,7025,7044,7045,7044,7026],[7024,7035,7025,7037,7024,7034,7036,7025],[7033,7030,7040,7034,7043,7033,7029,7028],[7045,7037,7036,7041,7033,7025,7035,7044],[7030,7042,7042,7040,7035,7029,7032,7041]]
Output: 6

Constraints:

1 <= text.length <= 50
1 <= width <= 1000
1 <= height <= 50
1 <= fonts.length <= 50
1 <= fonts[i] <= 50
cost[i].length == 26
1 <= cost[i][j] <= 10⁶
text contains only lowercase English letters.

Maximum Font to Fit a Sentence in a Screen

Medium

Asked by:

1 view

Topics:

Binary Search

You are given a string text. You want to display text on a screen of width width and height height. You can choose any font size from array fonts where each font size is the height of the font. You can choose any font size you want to display text.

You can only use one font size. After that, you will have to decide how many lines you want to display the text. The length of each line must be equal or less than width. You are also given a function cost that determines the cost of each character with a certain font size. cost[i][j] is the cost of character j with font size fonts[i]. You should choose the smallest font size and the minimum number of lines to display text with the lowest cost.

Return the font size you choose to display text with the lowest cost. If there is no way to display text on the screen, return -1.

Note:

You can break lines at any character.
Please remember that the height of the screen is height and the width is width.

Example 1:

Input: text = "abc", width = 5, height = 10, fonts = [1,2,3,4,5], cost = [[1,2,3],[2,3,4],[3,4,5],[4,5,6],[5,6,7]]
Output: 2
Explanation:
The screen looks like this if we choose font size 1:
abc
The screen looks like this if we choose font size 2:
ab
c
The screen looks like this if we choose font size 3:
ab
c
The screen looks like this if we choose font size 4:
ab
c
The screen looks like this if we choose font size 5:
ab
c
We should choose font size 2 because it has the minimum cost.

Example 2:

Input: text = "abc", width = 5, height = 10, fonts = [1,2], cost = [[1,2,3],[2,3,4]]
Output: 1
Explanation:
The screen looks like this if we choose font size 1:
abc
The screen looks like this if we choose font size 2:
ab
c
We can choose font size 1 or font size 2 but font size 1 has the lowest cost.

Example 3:

Input: text = "leetcode", width = 6, height = 5, fonts = [3,4,5,6,7,8,9,10], cost = [[7026,7045,7032,7041,7025,7033,7023,7038],[7039,7042,7030,7047,7042,7036,7044,7032],[7041,7040,7039,7036,7026,7024,7032,7030],[7045,7044,7033,7025,7044,7045,7044,7026],[7024,7035,7025,7037,7024,7034,7036,7025],[7033,7030,7040,7034,7043,7033,7029,7028],[7045,7037,7036,7041,7033,7025,7035,7044],[7030,7042,7042,7040,7035,7029,7032,7041]]
Output: 6

Constraints:

1 <= text.length <= 50
1 <= width <= 1000
1 <= height <= 50
1 <= fonts.length <= 50
1 <= fonts[i] <= 50
cost[i].length == 26
1 <= cost[i][j] <= 10⁶
text contains only lowercase English letters.

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What are the data types and value ranges for the font sizes and the screen dimensions (width and height)? Can they be floating-point numbers or only integers?
Can the input sentence be empty or null? What should I return in such a case?
If no font size allows the sentence to fit within the screen, what value should be returned?
Is there a predefined range of font sizes to consider, or is the search space unbounded? If there's a predefined range, what are its minimum and maximum values?
How is the sentence rendered? Do I need to account for any padding or margins around the text within the screen's boundaries?

Brute Force Solution

Approach

The brute force approach involves trying every possible font size to see if the sentence fits within the screen. We'll start with the smallest font size and incrementally increase it, checking if the sentence fits for each size. The largest font size that allows the entire sentence to fit on the screen is the maximum font size.

Here's how the algorithm would work step-by-step:

Start with the smallest possible font size.
Using this font size, figure out how much space the sentence will take up on the screen.
Check if the sentence, with this font size, fits entirely within the screen's available space.
If it does fit, remember this font size, because it's a candidate for the maximum.
Now, increase the font size by a small amount.
Repeat the process of calculating the space the sentence takes up and checking if it fits.
Continue increasing the font size and checking until the sentence no longer fits on the screen.
Once the sentence no longer fits, the largest font size we remembered before is the answer.

Code Implementation

def find_max_font_brute_force(sentence, screen_width, max_font_size):
    smallest_font_size = 1
    current_font_size = smallest_font_size
    max_font_size_that_fits = 0

    while current_font_size <= max_font_size:
        # Calculate the width of the sentence with the current font size.
        sentence_width = calculate_sentence_width(sentence, current_font_size)

        # Check if the sentence fits within the screen width.
        if sentence_width <= screen_width:
            # If it fits, update the maximum font size that fits.
            max_font_size_that_fits = current_font_size

            # Increment font size to check the next larger size.
            current_font_size += 1

        else:
            # Sentence does not fit, return the last font size that did fit
            break

    return max_font_size_that_fits

def calculate_sentence_width(sentence, font_size):
    # This is a placeholder function.
    # In a real scenario, this function would calculate
    # the actual width of the sentence based on the font size
    # and font properties.
    return len(sentence) * font_size

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

O(f) – The algorithm iterates through possible font sizes, starting from a minimum and incrementing until the sentence no longer fits. Let 'f' represent the range of possible font sizes that need to be checked. For each font size, we calculate the rendered sentence width, which takes a constant amount of time. The number of iterations is directly proportional to the range of possible font sizes considered, making the time complexity O(f).

Space Complexity

O(1) – The described algorithm primarily uses a single variable to store the largest font size that fits (the 'remembered' font size). While font size is incremented and tested, these are scalar values and do not depend on the input sentence's length, denoted here as N. No auxiliary data structures like arrays or hash maps are created. Therefore, the space complexity is constant, irrespective of the input size N.

Optimal Solution

Approach

The most efficient way to find the biggest font that fits is to avoid checking every possible font size. Instead, we'll use a method that quickly narrows down the possibilities, like guessing a number in a specific range, getting feedback on whether our guess is too high or too low, and adjusting our guess accordingly until we find the right fit.

Here's how the algorithm would work step-by-step:

Start by picking a font size somewhere in the middle of the possible range.
Test if the whole sentence fits on the screen using that font size.
If the sentence fits, try a bigger font size. If it doesn't fit, try a smaller font size.
Keep repeating the process of guessing a font size and checking if the sentence fits, each time getting closer to the biggest font size that still works.
Once we've narrowed it down enough, we'll have found the largest font size that allows the entire sentence to fit within the screen's boundaries.

Code Implementation

def maximum_font_size(sentence, screen_width, screen_height):
    min_font_size = 1
    max_font_size = 100

    while min_font_size <= max_font_size:
        
        mid_font_size = (min_font_size + max_font_size) // 2
        
        if fits_on_screen(sentence, mid_font_size, screen_width, screen_height):
            # If it fits, try a larger font size
            min_font_size = mid_font_size + 1
        else:
            # Otherwise, try a smaller font size
            max_font_size = mid_font_size - 1

    # Return the largest font size that fits.
    return max_font_size

def fits_on_screen(sentence, font_size, screen_width, screen_height):
    
    text_width, text_height = get_text_dimensions(sentence, font_size)
    # Check if text fits within screen boundaries.
    return text_width <= screen_width and text_height <= screen_height

def get_text_dimensions(sentence, font_size):
    
    text_width = len(sentence) * font_size  # Simplified width calculation
    text_height = font_size # Simplified height calculation
    # This assumes a simple character width calculation.
    return text_width, text_height

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

O(log n) – The algorithm employs a binary search approach to find the maximum font size. The input size 'n' represents the range of possible font sizes. In each iteration, the search space is halved. Therefore, the number of iterations required to find the solution is proportional to the logarithm base 2 of 'n', making the time complexity O(log n).

Space Complexity

O(1) – The algorithm primarily uses variables to store the current font size guess, the lower bound, and the upper bound of the font size range. Since it does not create auxiliary data structures like lists, arrays, or hash maps whose size depends on the input sentence or screen dimensions, the space used remains constant. Therefore, the space complexity is O(1).

Edge Cases

Case	How to Handle
Empty sentence or null sentence	Return 0 (or an appropriate error value/exception) as no font size can be determined for an empty sentence.
Empty screen dimensions (zero width or height)	Return 0 (or an appropriate error value/exception) as the sentence cannot fit in a screen with zero dimensions.
Sentence longer than the maximum allowed length (very large string)	Ensure the algorithm scales efficiently (e.g., using binary search) and consider potential memory limitations.
Screen size smaller than a single character at minimum font size	Return 0 (or an appropriate error value/exception) if the smallest font size makes the sentence too big.
Very long words in sentence that exceed screen width even at smallest font size	Return 0 (or an appropriate error value/exception) because the sentence will not fit.
Integer overflow when calculating sentence width or height for large font sizes	Use a data type capable of holding large values (e.g., long) and check for overflow conditions before proceeding.
Floating-point precision issues when calculating sentence dimensions at different font sizes	Use integer arithmetic where possible or a suitable epsilon when comparing floating-point numbers to screen dimensions.
Maximum font size doesn't fit the sentence, but slightly smaller font size does	Binary search correctly handles the edge case where the target is not directly found, converging to the largest possible font size that fits within the given screen dimensions