Maximum Font to Fit a Sentence in a Screen

Maximum Font to Fit a Sentence in a Screen - Problem

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.

Input & Output

Example 1 — Basic Case

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

› Output: 6

💡 Note: Font size 6 is the largest that fits within width 80 and height 20 for text 'helloworld'

Example 2 — No Font Fits

$ Input: text = "leetcode", w = 10, h = 5, fonts = [10,12,14,16,18,20]

› Output: -1

💡 Note: Even the smallest font (10) is too big for the tiny screen dimensions

Example 3 — Large Screen

$ Input: text = "a", w = 1000, h = 1000, fonts = [1,2,4,8,16,32,64]

› Output: 64

💡 Note: Single character 'a' can use the largest available font size on this large screen

Constraints

1 ≤ text.length ≤ 50000
text contains only lowercase English letters
1 ≤ w ≤ 10⁷
1 ≤ h ≤ 10⁴
1 ≤ fonts.length ≤ 10⁵
1 ≤ fonts[i] ≤ 10⁵
fonts is sorted in ascending order and does not contain duplicates

Visualization

Tap to expand

Understanding the Visualization

Input

Text string, screen width/height, available font sizes

Process

Test font sizes to find maximum that fits

Output

Return largest fitting font size or -1

Key Takeaway

🎯 Key Insight: Use binary search on sorted font sizes to efficiently find the maximum size that fits both width and height constraints

Asked in

G Google 12 f Facebook 8 a Amazon 5

The key insight is that font sizes are sorted, so we can use binary search to find the maximum font size that fits. The optimal approach uses binary search on the answer space to check font sizes efficiently. Time: O(log n × m), Space: O(1).

Common Approaches

Approach	Time	Space	Notes
✓ Linear Search (Brute Force)	O(n × m)	O(1)	Try each font size from largest to smallest until one fits
Binary Search on Answer	O(log n × m)	O(1)	Binary search on font sizes to find the maximum fitting size

Linear Search (Brute Force) — Algorithm Steps

Start from the largest font size
Calculate total width and height for current font
If it fits within screen bounds, return this font size
Otherwise try the next smaller font size
Return -1 if no font size works

Visualization

Tap to expand

Step-by-Step Walkthrough

Start Large

Begin with largest font size

Check Fit

Calculate width and height for current font

Found

Return first font size that fits

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef struct {
    int (*getWidth)(int fontSize, char ch);
    int (*getHeight)(int fontSize);
} FontInfo;

int solution(char* text, int w, int h, int* fonts, int fontsSize, FontInfo* fontInfo) {
    // Try font sizes from largest to smallest
    for (int i = fontsSize - 1; i >= 0; i--) {
        int fontSize = fonts[i];
        
        // Calculate height
        int textHeight = fontInfo->getHeight(fontSize);
        if (textHeight > h) continue;
        
        // Calculate width
        int textWidth = 0;
        for (int j = 0; j < strlen(text); j++) {
            textWidth += fontInfo->getWidth(fontSize, text[j]);
        }
        
        // Check if it fits
        if (textWidth <= w) {
            return fontSize;
        }
    }
    
    return -1;
}

int main() {
    char text[1000];
    fgets(text, sizeof(text), stdin);
    text[strcspn(text, "\n")] = 0;
    
    int w, h;
    scanf("%d", &w);
    scanf("%d", &h);
    
    // Simple parsing for fonts array
    int fonts[100];
    int fontsSize = 0;
    // Note: Simplified parsing for template
    
    int result = solution(text, w, h, fonts, fontsSize, NULL);
    printf("%d\n", result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n × m)

n font sizes × m characters in text for width calculation

✓ Linear Growth

Space Complexity

O(1)

Only using constant extra variables

✓ Linear Space

28.4K Views

Medium Frequency

~25 min Avg. Time

856 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Linear Search (Brute Force) — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler