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 <= 50000text contains only lowercase English letters.1 <= w <= 1071 <= h <= 1041 <= fonts.length <= 1051 <= fonts[i] <= 105fonts is sorted in ascending order and does not contain duplicates.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).
Python
Java
C++
JavaScript
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Linear Scan of Fonts | O(n * m) | O(1) | When the font list is small or quick implementation is preferred |
| Binary Search on Font Size | O(m log n) | O(1) | Best general solution when fonts are sorted and API calls are expensive |
1618. Maximum Font to Fit a Sentence in a Screen (Leetcode Medium) • Programming Live with Larry • 141 views views
Watch 2 more video solutions →Practice Maximum Font to Fit a Sentence in a Screen with our built-in code editor and test cases.
Practice on FleetCode