Problem Description

You are given a string text that represents a sentence, an array fonts of available font sizes (integers, sorted in descending order), and a 2D array fontInfo. Each entry in fontInfo is an array of 3 integers: [fontSize, widthPerChar, height], describing the width of each character and height for that font size. You are also given two integers w and h, representing the width and height of a screen in pixels.

Your task is to find the maximum font size from fonts that allows the entire text to fit inside the screen, meaning:

• The total width of the sentence (number of characters × width per character for the font) does not exceed w.
• The height of the font does not exceed h.

If no font size fits, return -1. You are guaranteed that fonts contains only unique font sizes and fontInfo contains information for all font sizes in fonts.

Thought Process

The core challenge is to find the largest font size that fits both width and height constraints. A brute-force approach would be to try each font size from largest to smallest, check if the sentence fits, and return the first valid size. This is feasible because the number of fonts is usually small.

However, we can optimize further. Since fonts is sorted in descending order, we can use binary search to quickly find the maximum valid font size. This reduces unnecessary checks and speeds up the process.

The main steps are:

• Efficiently map each font size to its width and height info.
• Check the fit for each font size (width and height).
• Use binary search to optimize the search for the largest fitting font.

Solution Approach

Let's break down the solution step by step:

1. Build a Lookup Table:
   • Create a mapping from font size to its corresponding [widthPerChar, height] using a hash map (dictionary). This allows O(1) lookup for each font's info.
2. Binary Search for Maximum Font:
   • Since fonts is sorted in descending order, we can perform binary search to find the largest font size that fits.
   • For each candidate font size, calculate:
     • totalWidth = len(text) × widthPerChar
     • height (from font info)
   • If both totalWidth ≤ w and height ≤ h, this font fits.
   • Continue searching for a larger font (move binary search window accordingly).
3. Return Result:
   • If a valid font is found, return its size. If not, return -1.

This method is efficient because:

• Hash map lookups are O(1).
• Binary search over N fonts is O(log N).
• All calculations per font are constant time.

Example Walkthrough

Suppose text = "leetcode", fonts = [28,24,20,18,14,10], fontInfo = [[28,2,4],[24,2,3],[20,1,3],[18,1,2],[14,1,2],[10,1,1]], w = 50, h = 6.

• Build a mapping: {28: [2,4], 24: [2,3], 20: [1,3], ...}
• Binary search - check middle font (20): width = 8×1 = 8, height = 3. Both fit.
• Try higher font (24): width = 8×2 = 16, height = 3. Both fit.
• Try even higher (28): width = 8×2 = 16, height = 4. Both fit.
• Since 28 is the largest, return 28.

If the screen was smaller (e.g., w=10), none of the larger fonts would fit, and the binary search would continue to lower values until either a fit is found or -1 is returned.

Time and Space Complexity

Brute-force approach:

• Try each font from largest to smallest: O(N), where N is the number of fonts.
• Each check is O(1).
• Total: O(N).

• Build the hash map: O(N).
• Binary search: O(log N) checks.
• Each check is O(1).
• Total: O(N) for setup + O(log N) for search.

• Hash map: O(N).

Summary

The problem asks for the largest font size that allows a sentence to fit within given screen dimensions. By mapping font sizes to their properties and using binary search, we efficiently find the optimal solution. The key insight is leveraging the sorted font sizes and using hash maps for quick lookups, making the solution both simple and fast.

Code Implementation

class Solution:
    def maxFont(self, text, fonts, fontInfo, w, h):
        # Build font info dictionary: font size -> (width per char, height)
        font_map = {size: (width, height) for size, width, height in fontInfo}
        left, right = 0, len(fonts) - 1
        res = -1
        while left <= right:
            mid = (left + right) // 2
            font_size = fonts[mid]
            width, height = font_map[font_size]
            total_width = len(text) * width
            if total_width <= w and height <= h:
                res = font_size
                left = mid + 1
            else:
                right = mid - 1
        return res
      

class Solution {
public:
    int maxFont(string text, vector<int>& fonts, vector<vector<int>>& fontInfo, int w, int h) {
        unordered_map<int, pair<int, int>> fontMap;
        for (auto& info : fontInfo) {
            fontMap[info[0]] = {info[1], info[2]};
        }
        int left = 0, right = fonts.size() - 1, res = -1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            int fontSize = fonts[mid];
            int width = fontMap[fontSize].first;
            int height = fontMap[fontSize].second;
            int totalWidth = text.size() * width;
            if (totalWidth <= w && height <= h) {
                res = fontSize;
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        return res;
    }
};
      

class Solution {
    public int maxFont(String text, int[] fonts, int[][] fontInfo, int w, int h) {
        Map<Integer, int[]> fontMap = new HashMap<>();
        for (int[] info : fontInfo) {
            fontMap.put(info[0], new int[]{info[1], info[2]});
        }
        int left = 0, right = fonts.length - 1, res = -1;
        while (left <= right) {
            int mid = (left + right) / 2;
            int fontSize = fonts[mid];
            int[] info = fontMap.get(fontSize);
            int totalWidth = text.length() * info[0];
            if (totalWidth <= w && info[1] <= h) {
                res = fontSize;
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        return res;
    }
}
      

var maxFont = function(text, fonts, fontInfo, w, h) {
    const fontMap = new Map();
    for (const [size, width, height] of fontInfo) {
        fontMap.set(size, [width, height]);
    }
    let left = 0, right = fonts.length - 1, res = -1;
    while (left <= right) {
        const mid = Math.floor((left + right) / 2);
        const fontSize = fonts[mid];
        const [width, height] = fontMap.get(fontSize);
        const totalWidth = text.length * width;
        if (totalWidth <= w && height <= h) {
            res = fontSize;
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    return res;
};