Skip to main content
Talentd

Maximum Font to Fit a Sentence in a Screen - Solution & Explanation

MediumPremiumFree on FleetCodeArrayStringBinary SearchInteractive7 min readAsked at: Google
Practice this problem

Problem Statement

You are given a string text. We want to display text on a screen of width w and height h. You can choose any font size from array fonts, which contains the available font sizes in ascending order.

You can use the FontInfo interface to get the width and height of any character at any available font size.

The FontInfo interface is defined as such:


interface FontInfo {

  // Returns the width of character ch on the screen using font size fontSize.

  // O(1) per call

  public int getWidth(int fontSize, char ch);



  // Returns the height of any character on the screen using font size fontSize.

  // O(1) per call

  public int getHeight(int fontSize);

}

The calculated width of text for some fontSize is the sum of every getWidth(fontSize, text[i]) call for each 0 <= i < text.length (0-indexed). The calculated height of text for some fontSize is getHeight(fontSize). Note that text is displayed on a single line.

It is guaranteed that FontInfo will return the same value if you call getHeight or getWidth with the same parameters.

It is also guaranteed that for any font size fontSize and any character ch:

  • getHeight(fontSize) <= getHeight(fontSize+1)
  • getWidth(fontSize, ch) <= getWidth(fontSize+1, ch)

Return the maximum font size you can use to display text on the screen. If text cannot fit on the display with any font size, return -1.

 

Example 1:


Input: text = "helloworld", w = 80, h = 20, fonts = [6,8,10,12,14,16,18,24,36]

Output: 6

Example 2:


Input: text = "leetcode", w = 1000, h = 50, fonts = [1,2,4]

Output: 4

Example 3:


Input: text = "easyquestion", w = 100, h = 100, fonts = [10,15,20,25]

Output: -1

 

Constraints:

  • 1 <= text.length <= 50000
  • text contains only lowercase English letters.
  • 1 <= w <= 107
  • 1 <= h <= 104
  • 1 <= fonts.length <= 105
  • 1 <= fonts[i] <= 105
  • fonts is sorted in ascending order and does not contain duplicates.

Approach Overview

Problem Overview: You’re given a sentence, screen width w, screen height h, and a sorted list of available font sizes. Using a provided FontInfo API, determine the largest font size that allows the entire sentence to fit within the screen constraints.

Approach 1: Linear Scan of Fonts (O(n * m) time, O(1) space)

Start from the smallest font and test each font size sequentially. For a candidate font, call getHeight(font) to ensure the font height does not exceed h. Then iterate through every character in the sentence and sum getWidth(font, c). If the total width exceeds w, the font does not fit. Continue scanning until fonts stop fitting and return the last valid one. This approach is simple and works because fonts are already sorted, but it may call the API many times when the font list is large.

Approach 2: Binary Search on Font Size (O(m log n) time, O(1) space)

The font array is sorted, which makes it perfect for binary search. Instead of testing every font, search for the largest valid font. For each mid font, first check getHeight(mid). If the height exceeds h, discard the right half. Otherwise compute the total width by iterating over the sentence characters (a string traversal) and summing getWidth(mid, c). If the width fits within w, move right to try a larger font; otherwise move left. Binary search reduces the number of expensive API calls significantly while keeping the width calculation straightforward.

The key insight is monotonicity: if a font fits, every smaller font will also fit. That property allows binary search to safely eliminate half of the candidate fonts each step.

Recommended for interviews: Binary search on the font array. Interviewers expect you to recognize the sorted input and the monotonic fit condition. Mentioning the linear scan first shows baseline reasoning, but implementing the binary search solution demonstrates stronger algorithmic thinking and reduces checks from O(n) to O(log n).

Solution

Code

PythonJavaC++JavaScript

Python

Java

C++

JavaScript

Try this approach in the editor →

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Linear Scan of FontsO(n * m)O(1)When the font list is small or quick implementation is preferred
Binary Search on Font SizeO(m log n)O(1)Best general solution when fonts are sorted and API calls are expensive

Video Solution

1618. Maximum Font to Fit a Sentence in a Screen (Leetcode Medium) • Programming Live with Larry • 143 views views

Watch 2 more video solutions →

Frequently Asked Questions

Is Maximum Font to Fit a Sentence in a Screen easy or hard?
The problem is generally classified as Medium difficulty. The main challenge is recognizing the monotonic property that allows binary search and efficiently validating whether a font fits within the width and height constraints.
Maximum Font to Fit a Sentence in a Screen Python/Java solution
Implement binary search over the fonts list and use the provided FontInfo API to validate each candidate. For each font, check getHeight(font) and iterate through the sentence calling getWidth(font, c). This logic is identical across Python, Java, C++, and JavaScript implementations.
How to solve Maximum Font to Fit a Sentence in a Screen in O(m log n)?
Use binary search over the sorted fonts array. For each midpoint font, first verify that getHeight(font) <= h. If it passes, iterate through the sentence and sum getWidth(font, c); if the total width <= w, move the search right to try larger fonts, otherwise move left. Track the largest valid font found.
What is the best approach for Maximum Font to Fit a Sentence in a Screen?
Binary search on the sorted font array is the most efficient approach. Each candidate font is validated by checking the height with getHeight(font) and summing character widths using getWidth(font, c). This reduces checks to O(log n) font candidates with O(m) width computation per check.
Is Maximum Font to Fit a Sentence in a Screen asked at Google/Amazon/Meta?
This problem is commonly associated with Google-style interview questions because it involves an external API and binary search optimization. The pattern of checking feasibility through an API while searching a monotonic space appears frequently in big tech interviews.
What data structure is used in Maximum Font to Fit a Sentence in a Screen?
The solution primarily uses arrays and strings. The fonts are stored in a sorted array, and the sentence is processed as a string to compute character widths. Binary search is applied on the array to efficiently locate the largest valid font.
What is the time complexity of Maximum Font to Fit a Sentence in a Screen?
The optimal solution runs in O(m log n) time, where n is the number of available fonts and m is the length of the sentence. Binary search selects candidate fonts while each validation scans the characters once to compute total width. Space complexity is O(1).

Ready to solve this problem?

Practice Maximum Font to Fit a Sentence in a Screen with our built-in code editor and test cases.

Practice on FleetCode
Previous

Two Sum

Next

Median of Two Sorted Arrays