Number of Lines To Write String

easy strings simulation

Problem

Given an array widths of 26 integers (width of 'a'..'z') and a string s, write s across as few lines as possible where each line is at most 100 units wide. Return [number_of_lines, width_of_last_line].

Inputwidths = [10]*26, s = "abcdefghijklmnopqrstuvwxyz"

Output[3, 60]

26 letters * 10 = 260 units = 3 lines (100, 100, 60).

s (letters a-z, widths fixed at 10 each)

def numberOfLines(widths, s):
    lines, cur = 1, 0
    for c in s:
        w = widths[ord(c) - ord('a')]
        if cur + w > 100:
            lines += 1
            cur = w
        else:
            cur += w
    return [lines, cur]

var numberOfLines = function(widths, s) {
    let lines = 1, cur = 0;
    for (const c of s) {
        const w = widths[c.charCodeAt(0) - 97];
        if (cur + w > 100) { lines++; cur = w; }
        else cur += w;
    }
    return [lines, cur];
};

class Solution {
    public int[] numberOfLines(int[] widths, String s) {
        int lines = 1, cur = 0;
        for (char c : s.toCharArray()) {
            int w = widths[c - 'a'];
            if (cur + w > 100) { lines++; cur = w; }
            else cur += w;
        }
        return new int[]{lines, cur};
    }
}

class Solution {
public:
    vector<int> numberOfLines(vector<int>& widths, string s) {
        int lines = 1, cur = 0;
        for (char c : s) {
            int w = widths[c - 'a'];
            if (cur + w > 100) { lines++; cur = w; }
            else cur += w;
        }
        return {lines, cur};
    }
};

Explanation

Imagine you are typing the string onto paper where every line can hold at most 100 units of width. You write letters left to right, and as soon as the next letter would not fit, you start a new line. This is a simple greedy simulation.

We keep two numbers: lines (how many lines used so far, starting at 1) and cur (the width already filled on the current line). Each letter c has its own width, found with widths[ord(c) - ord('a')].

For every letter we check cur + w > 100. If adding it overflows, we move to a fresh line: lines += 1 and reset cur = w (the letter now sits at the start of the new line). Otherwise it fits, so we just do cur += w.

At the end, cur is exactly the width used on the last line, so we return [lines, cur].

Example: all widths are 10 and s is "a".."z" (26 letters). Each line fits 10 letters (100 units), so the first two lines hold 20 letters and the remaining 6 letters use 60 units on line 3. Answer: [3, 60].

Time: O(n) Space: O(1)