LeetCode 1618 - Maximum Font to Fit a Sentence in a Screen

In this problem, we are given a string text that must be displayed on a single line inside a screen with width w and hei

leetcodemediumarraystringbinary-searchinteractive

LeetCode Problem 1618

Difficulty: 🟡 Medium
Topics: Array, String, Binary Search, Interactive

Solution

Problem Understanding

In this problem, we are given a string text that must be displayed on a single line inside a screen with width w and height h. We are also given a sorted array fonts, where each value represents an available font size that we are allowed to use.

The important detail is that the actual rendered dimensions of the text are not computed directly by us. Instead, we must use the provided FontInfo interface:

  • getWidth(fontSize, ch) returns the width of a single character ch when rendered using fontSize
  • getHeight(fontSize) returns the height of any character using fontSize

The width of the full string is the sum of the widths of all characters in text, because the text is displayed on a single line. The height of the string is simply the font height returned by getHeight(fontSize).

Our task is to determine the largest font size from fonts such that:

  • Total text width is less than or equal to w
  • Text height is less than or equal to h

If no font size satisfies both conditions, we return -1.

The constraints are large enough that efficiency matters:

  • text.length can be up to 50,000
  • fonts.length can be up to 100,000

A naive solution that checks every font and recomputes every character width repeatedly can become extremely expensive.

The problem also provides a very important monotonicity guarantee:

  • Character widths never decrease as font size increases
  • Font heights never decrease as font size increases

This monotonic behavior strongly suggests that binary search can be used.

Several edge cases are important:

  • Even the smallest font may not fit
  • Every font may fit, in which case we return the largest one
  • Width may fail while height passes
  • Height may fail while width passes
  • The string can contain repeated characters, causing many repeated getWidth calls in a naive implementation

Because the interface calls are theoretically constant time but still expensive in practice, minimizing unnecessary calls is valuable.

Approaches

Brute Force Approach

The most straightforward solution is to iterate through every font size in fonts from smallest to largest.

For each font:

  1. Check whether the height fits inside h
  2. Compute the total width of the string by summing the width of every character
  3. If both constraints are satisfied, update the answer

Since fonts is sorted, the last valid font encountered is the answer.

This approach is correct because it explicitly verifies every possible font size. However, it is inefficient because we may scan all font sizes, and for each one we may scan the entire string.

If:

  • F = len(fonts)
  • N = len(text)

then the complexity becomes O(F * N).

With both values large, this can become too slow.

Optimal Approach

The key observation is that the validity of a font size is monotonic.

If a font size fits on the screen, then every smaller font size also fits.

If a font size does not fit, then every larger font size also does not fit.

This creates a classic binary search condition.

We define a helper function:

  • can_fit(fontSize) returns whether the text fits within width w and height h

Then we binary search over the sorted fonts array to find the largest valid font.

Each binary search step checks one font size. The helper computes:

  • Height condition first
  • Width condition only if height passes

This gives a much more efficient solution.

Approach Comparison

Approach Time Complexity Space Complexity Notes
Brute Force O(F × N) O(1) Checks every font size sequentially
Optimal O(N × log F) O(1) Uses binary search on monotonic validity

Where:

  • F = len(fonts)
  • N = len(text)

Algorithm Walkthrough

  1. Define a helper function can_fit(font_size).

This function determines whether the text can fit inside the screen using the given font size. 2. Inside can_fit, first check the font height.

Call:

fontInfo.getHeight(font_size)

If the height exceeds h, return False immediately.

This early rejection is important because it avoids unnecessary width calculations. 3. Compute the total width of the text.

Iterate through every character in text and sum:

fontInfo.getWidth(font_size, ch)

If the running total exceeds w, stop early and return False. 4. If both height and width constraints pass, return True. 5. Perform binary search over the fonts array.

Since the array is sorted and validity is monotonic:

  • If a font fits, search the right half for a larger valid font
  • If a font does not fit, search the left half
  1. Maintain a variable answer.

Whenever a valid font is found, store it as the current best answer. 7. Continue until binary search finishes. 8. Return the stored answer.

If no font fits, the answer remains -1.

Why it works

The algorithm relies on the monotonic property of font validity.

If a particular font size fits:

  • All smaller font sizes must also fit because widths and heights never decrease.

If a particular font size does not fit:

  • All larger font sizes must also fail.

This creates a valid binary search space. Binary search guarantees that we find the largest valid font efficiently.

Python Solution

from typing import List

# """
# This is FontInfo's API interface.
# You should not implement it, or speculate about its implementation
# """
# class FontInfo(object):
#     def getWidth(self, fontSize, ch):
#         pass
#
#     def getHeight(self, fontSize):
#         pass

class Solution:
    def maxFont(
        self,
        text: str,
        w: int,
        h: int,
        fonts: List[int],
        fontInfo: 'FontInfo'
    ) -> int:

        def can_fit(font_size: int) -> bool:
            if fontInfo.getHeight(font_size) > h:
                return False

            total_width = 0

            for ch in text:
                total_width += fontInfo.getWidth(font_size, ch)

                if total_width > w:
                    return False

            return True

        left = 0
        right = len(fonts) - 1
        answer = -1

        while left <= right:
            mid = (left + right) // 2
            font_size = fonts[mid]

            if can_fit(font_size):
                answer = font_size
                left = mid + 1
            else:
                right = mid - 1

        return answer

The implementation closely follows the algorithm described earlier.

The can_fit helper encapsulates the validation logic for a single font size. It first checks height because height evaluation is constant time and can eliminate invalid fonts immediately.

The width computation uses a running sum. As soon as the width exceeds w, the function exits early. This avoids unnecessary interface calls for long strings.

The binary search operates on indices of the fonts array. Whenever a font fits, it becomes the current best answer and the search continues to the right to look for a larger valid font.

If a font does not fit, the search moves left because larger fonts will also fail due to monotonicity.

The final answer is returned after the binary search completes.

Go Solution

/**
 * // This is FontInfo's API interface.
 * // You should not implement it, or speculate about its implementation
 * type FontInfo struct {}
 *
 * func (f *FontInfo) GetWidth(fontSize int, ch byte) int {}
 *
 * func (f *FontInfo) GetHeight(fontSize int) int {}
 */

type Solution struct{}

func (s *Solution) maxFont(
	text string,
	w int,
	h int,
	fonts []int,
	fontInfo FontInfo,
) int {

	canFit := func(fontSize int) bool {
		if fontInfo.GetHeight(fontSize) > h {
			return false
		}

		totalWidth := 0

		for i := 0; i < len(text); i++ {
			totalWidth += fontInfo.GetWidth(fontSize, text[i])

			if totalWidth > w {
				return false
			}
		}

		return true
	}

	left := 0
	right := len(fonts) - 1
	answer := -1

	for left <= right {
		mid := left + (right-left)/2
		fontSize := fonts[mid]

		if canFit(fontSize) {
			answer = fontSize
			left = mid + 1
		} else {
			right = mid - 1
		}
	}

	return answer
}

The Go implementation mirrors the Python logic almost exactly.

One small language difference is that Go strings are indexed as bytes. Since the problem guarantees lowercase English letters only, using text[i] as a byte is completely safe.

The binary search uses:

mid := left + (right-left)/2

which avoids potential integer overflow in general binary search implementations.

Go also uses explicit variable declarations and typed slices instead of Python lists.

Worked Examples

Example 1

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

Suppose binary search proceeds as follows.

Step Mid Font Fits? Action
1 14 No Search left
2 8 No Search left
3 6 Yes Store answer, search right

Final answer is 6.

At font size 6:

Check Result
Height ≤ 20
Total Width ≤ 80

At font size 8, width exceeds 80, so it fails.

Example 2

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

All fonts fit.

Step Mid Font Fits? Action
1 2 Yes Search right
2 4 Yes Search right

Largest valid font is 4.

Example 3

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

No font fits.

Step Mid Font Fits? Action
1 15 No Search left
2 10 No Search left

Since no valid font exists, return -1.

Complexity Analysis

Measure Complexity Explanation
Time O(N × log F) Binary search performs O(log F) checks, each scanning up to N characters
Space O(1) Only constant extra variables are used

The binary search reduces the number of font checks dramatically compared to the brute force approach.

Each validity check may scan the entire string in the worst case, though early termination often improves practical performance.

No auxiliary data structures proportional to input size are used, so the algorithm requires constant extra space.

Test Cases

class MockFontInfo:
    def getWidth(self, fontSize, ch):
        return fontSize

    def getHeight(self, fontSize):
        return fontSize

solution = Solution()
fontInfo = MockFontInfo()

# Example 1
assert solution.maxFont(
    "helloworld",
    80,
    20,
    [6, 8, 10, 12, 14, 16, 18, 24, 36],
    fontInfo
) == 8  # largest fitting font with mock widths

# Example 2
assert solution.maxFont(
    "leetcode",
    1000,
    50,
    [1, 2, 4],
    fontInfo
) == 4  # all fonts fit

# Example 3
assert solution.maxFont(
    "easyquestion",
    100,
    100,
    [10, 15, 20, 25],
    fontInfo
) == -1  # none fit

# Single character
assert solution.maxFont(
    "a",
    10,
    10,
    [1, 5, 10],
    fontInfo
) == 10  # exact fit

# Height fails but width passes
assert solution.maxFont(
    "abc",
    1000,
    4,
    [2, 4, 6, 8],
    fontInfo
) == 4  # height restriction

# Width fails but height passes
assert solution.maxFont(
    "abcdefghij",
    25,
    100,
    [1, 2, 3, 4],
    fontInfo
) == 2  # width restriction

# Smallest font barely fits
assert solution.maxFont(
    "abcd",
    4,
    1,
    [1, 2, 3],
    fontInfo
) == 1  # boundary fit

# Empty answer case
assert solution.maxFont(
    "zzzz",
    1,
    1,
    [2, 3, 4],
    fontInfo
) == -1  # impossible case

# Large width allows largest font
assert solution.maxFont(
    "abc",
    100000,
    100000,
    [10, 20, 30, 40],
    fontInfo
) == 40  # maximum font valid
Test Why
Example 1 Verifies normal binary search behavior
Example 2 Verifies all fonts fit
Example 3 Verifies no valid font exists
Single character Tests minimal string length
Height fails but width passes Ensures height constraint is checked correctly
Width fails but height passes Ensures width accumulation works
Smallest font barely fits Tests exact boundary handling
Empty answer case Confirms -1 is returned correctly
Large width allows largest font Verifies maximum valid font is returned

Edge Cases

One important edge case occurs when no font size fits. A buggy implementation might accidentally return the smallest font or fail to initialize the answer correctly. In this solution, answer starts as -1 and is updated only when a valid font is found, ensuring the correct behavior.

Another critical edge case is when the height constraint fails immediately. Since height is monotonic and independent of text length, checking it before computing widths prevents unnecessary work. This optimization is especially important when text is very large.

A third important edge case involves exact boundary fits. The text is allowed to occupy exactly width w and height h. The implementation correctly uses > comparisons rather than >=, meaning equality is treated as valid.

A subtle performance-related edge case occurs with extremely long strings. A naive implementation may continue summing widths even after exceeding w. This solution stops immediately once the width becomes too large, avoiding unnecessary interface calls.

Another important scenario is when every font fits. The binary search continues moving right whenever a valid font is found, guaranteeing that the largest valid font is returned rather than the first one encountered.