How hard is LeetCode 1618. Maximum Font to Fit a Sentence in a Screen?

LeetCode 1618. Maximum Font to Fit a Sentence in a Screen is rated Medium on LeetCode.

What topics does LeetCode 1618. Maximum Font to Fit a Sentence in a Screen cover?

LeetCode 1618. Maximum Font to Fit a Sentence in a Screen is tagged Array, String, Binary Search and Interactive on LeetCode.

Is LeetCode 1618. Maximum Font to Fit a Sentence in a Screen a premium problem?

Yes. LeetCode 1618. Maximum Font to Fit a Sentence in a Screen is a LeetCode Premium problem, so the full statement and test cases require a paid LeetCode subscription.

Maximum Font to Fit a Sentence in a Screen — LeetCode 1618 Python Solution

MediumLeetCode PremiumArrayStringBinary SearchInteractive

Problem: #1618
Pattern: Monotonic Stack
Reading time: 6 min
Source: leetcode.com

The problem

You are given a string text. We want to display text on a screen of width w and height h.

Example

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);

}

Python solution

Python

# """
# This is FontInfo's API interface.
# You should not implement it, or speculate about its implementation
# """
# class FontInfo(object):
#    Return the width of char ch when fontSize is used.
#    def getWidth(self, fontSize, ch):
#        """
#        :type fontSize: int
#        :type ch: char
#        :rtype int
#        """
#
#    def getHeight(self, fontSize):
#        """
#        :type fontSize: int
#        :rtype int
#        """
class Solution:
    def maxFont(
        self, text: str, w: int, h: int, fonts: List[int], fontInfo: 'FontInfo'
    ) -> int:
        def check(size):
            if fontInfo.getHeight(size) > h:
                return False
            return sum(fontInfo.getWidth(size, c) for c in text) <= w

        left, right = 0, len(fonts) - 1
        ans = -1
        while left < right:
            mid = (left + right + 1) >> 1
            if check(fonts[mid]):
                left = mid
            else:
                right = mid - 1
        return fonts[left] if check(fonts[left]) else -1

Complexity

Measure	Complexity
Time	O(log n) or O(n log n)
Space	O(1) auxiliary

Pattern: Monotonic Stack

Answer "what is the next greater element" for every position in one pass. LeetCode 1618. Maximum Font to Fit a Sentence in a Screen is filed here because the reference solution below belongs to the algorithm family this hub collects, even though its LeetCode tags point elsewhere.

The monotonic stack guide has the Python template for the pattern and the 225 LeetCode problems that use it.

Frequently asked questions

How hard is LeetCode 1618. Maximum Font to Fit a Sentence in a Screen?: LeetCode 1618. Maximum Font to Fit a Sentence in a Screen is rated Medium on LeetCode.
What topics does LeetCode 1618. Maximum Font to Fit a Sentence in a Screen cover?: LeetCode 1618. Maximum Font to Fit a Sentence in a Screen is tagged Array, String, Binary Search and Interactive on LeetCode.
Is LeetCode 1618. Maximum Font to Fit a Sentence in a Screen a premium problem?: Yes. LeetCode 1618. Maximum Font to Fit a Sentence in a Screen is a LeetCode Premium problem, so the full statement and test cases require a paid LeetCode subscription.