1618

/**
 * // This is the FontInfo's API interface.
 * // You should not implement it, or speculate about its implementation
 * class FontInfo {
 *   public:
 *     // Return the width of char ch when fontSize is used.
 *     int getWidth(int fontSize, char ch);
 *
 *     // Return Height of any char when fontSize is used.
 *     int getHeight(int fontSize)
 * };
 */
class Solution {
public:
    int maxFont(string text, int w, int h, vector<int>& fonts, FontInfo fontInfo) {
        int l=0, r=fonts.size();

        while(l<r){
            int mid = (l+r)/2;
            int height = fontInfo.getHeight(fonts[mid]);
            if(height > h || getWidth(fontInfo, fonts[mid], text) > w){
                r = mid;
            }
            else{
                l = mid+1;
            }
        }
        if(!r) return -1;
        return fonts[r-1];
    }

    int getWidth(FontInfo f, int fontSize, string &txt){
        int width = 0;
        int w[26];
        for(int i=0; i<26; i++)
            w[i] = f.getWidth(fontSize, 'a'+i);

        for(int i=0; i<txt.size(); i++)
            width += w[txt[i]-'a'];

        return width;
    }

};