We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Maximum Font to Fit a Sentence in a Screen

Number: 1384

Difficulty: Medium

Paid? Yes

Companies: Google

Problem Description

Given a string text and a screen with width w and height h, choose a font size from a sorted array fonts such that when text is displayed on a single line using that font, the total width (sum of character widths) does not exceed w and the height (given by FontInfo.getHeight for that font) does not exceed h. Each character's width is given by FontInfo.getWidth(fontSize, character). The goal is to return the maximum font size from fonts that allows the text to fit; return -1 if no font works.

Key Insights

  • The fonts array is sorted in ascending order; therefore, a binary search is an efficient way to find the maximum valid font size.
  • For each candidate font, check if:
    • The height (FontInfo.getHeight(font)) is within h.
    • The total width (sum over text characters using FontInfo.getWidth(font, ch)) is within w.
  • If a candidate font fits, search for a larger font size; if not, search for a smaller one.

Space and Time Complexity

Time Complexity: O(n log m) where n is the length of text and m is the number of available fonts. Each binary search iteration checks the entire text. Space Complexity: O(1) extra space aside from the input.

Solution

Use binary search on the sorted fonts array. For each candidate font size, use the provided FontInfo interface to check if the text can be displayed within the screen dimensions. A helper function (fits) calculates the total width by iterating over the text and compares the font height. If the candidate font fits, update the result and try a larger font; otherwise, try a smaller font. This efficiently finds the maximum valid font size.

Code Solutions

def maximumFont(text, w, h, fonts, fontInfo):
    # Helper function to check if text fits using the given font size.
    def fits(font_size):
        # Check if the font's height exceeds the available height.
        if fontInfo.getHeight(font_size) > h:
            return False
        total_width = 0
        # Calculate the total width for all characters.
        for ch in text:
            total_width += fontInfo.getWidth(font_size, ch)
            # Early return if the width exceeds the screen's width.
            if total_width > w:
                return False
        return True

    left, right = 0, len(fonts) - 1
    result = -1
    # Use binary search to find the maximum font size that fits.
    while left <= right:
        mid = (left + right) // 2
        if fits(fonts[mid]):
            result = fonts[mid]  # This font size works, try to find a larger one.
            left = mid + 1
        else:
            right = mid - 1
    return result
← Back to All Questions