1618. Maximum Font to Fit a Sentence in a Screen

T: O(nlogn)
S: O(1)

/**
 * // This is the FontInfo's API interface.
 * // You should not implement it, or speculate about its implementation
 * interface FontInfo {
 *     // Return the width of char ch when fontSize is used.
 *     public int getWidth(int fontSize, char ch) {}
 *     // Return Height of any char when fontSize is used.
 *     public int getHeight(int fontSize)
 * }
 */
class Solution {
    public int maxFont(String text, int w, int h, int[] fonts, FontInfo fontInfo) {
        int left = 0;
        int right = fonts.length - 1;
        
        while (left + 1 < right) {
            int mid = left + (right - left)/2;

            if (isOK(text, fonts[mid], w, h, fontInfo)) { // is <= w, <= h, so font can be larger
                left = mid;
            } else {
                right = mid;
            }
        }
        // we want larger one
        if (isOK(text, fonts[right], w, h, fontInfo)) {
            return fonts[right];
        }
        if (isOK(text, fonts[left], w, h, fontInfo)) {
            return fonts[left];
        }
        return -1;
    }
    
    /*
    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).
    */
    private int calWidth(String text, int font, FontInfo fontInfo) {
        int width = 0;
        for (char c : text.toCharArray()) {
            width += fontInfo.getWidth(font, c);
        }
        return width;
    }
    // so just check is inside w, h
    private boolean isOK(String text, int font, int w, int h, FontInfo fontInfo) {
        return calWidth(text, font, fontInfo) <= w && fontInfo.getHeight(font) <= h;
    }
}

/*
Return the maximum font size you can use to display text on the screen


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

binary search to find suitable font from fonts[]
T: O(nlogn)
S: O(1)
*/