Problem

You are given a string s of lowercase English letters and an array widths denoting how many pixels wide each lowercase English letter is. Specifically, widths[0] is the width of 'a', widths[1] is the width of 'b', and so on.

You are trying to write s across several lines, where each line is no longer than100pixels. Starting at the beginning of s, write as many letters on the first line such that the total width does not exceed 100 pixels. Then, from where you stopped in s, continue writing as many letters as you can on the second line. Continue this process until you have written all of s.

Return an arrayresult of length 2 where:

  • result[0]is the total number of lines.
  • result[1]is the width of the last line in pixels.

Examples

Example 1

1
2
3
4
5
6
7

Input: widths = [10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10], s = "abcdefghijklmnopqrstuvwxyz"
Output: [3,60]
Explanation: You can write s as follows:
abcdefghij  // 100 pixels wide
klmnopqrst  // 100 pixels wide
uvwxyz      // 60 pixels wide
There are a total of 3 lines, and the last line is 60 pixels wide.

Example 2

1
2
3
4
5
6

Input: widths = [4,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10], s = "bbbcccdddaaa"
Output: [2,4]
Explanation: You can write s as follows:
bbbcccdddaa  // 98 pixels wide
a            // 4 pixels wide
There are a total of 2 lines, and the last line is 4 pixels wide.

Constraints

  • widths.length == 26
  • 2 <= widths[i] <= 10
  • 1 <= s.length <= 1000
  • s contains only lowercase English letters.

Solution

Method 1 – Greedy Line Packing

Intuition

We want to fit as many letters as possible on each line without exceeding 100 pixels. For each character, add its width to the current line; if it exceeds 100, start a new line.

Approach

  1. Initialize line count and current width.
  2. For each character in s, add its width to current width.
  3. If current width exceeds 100, increment line count and reset current width to the character’s width.
  4. Return total lines and last line width.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

#include <vector>
#include <string>
using namespace std;
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};
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

func numberOfLines(widths []int, s string) []int {
    lines, cur := 1, 0
    for i := 0; i < len(s); i++ {
        w := widths[s[i]-'a']
        if cur + w > 100 {
            lines++; cur = w
        } else {
            cur += w
        }
    }
    return []int{lines, cur}
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

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};
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

class Solution {
    fun numberOfLines(widths: IntArray, s: String): IntArray {
        var lines = 1; var cur = 0
        for (c in s) {
            val w = widths[c-'a']
            if (cur + w > 100) { lines++; cur = w }
            else cur += w
        }
        return intArrayOf(lines, cur)
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10

class Solution:
    def numberOfLines(self, widths: list[int], s: str) -> list[int]:
        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]
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

impl Solution {
    pub fn number_of_lines(widths: Vec<i32>, s: String) -> Vec<i32> {
        let mut lines = 1;
        let mut cur = 0;
        for c in s.chars() {
            let w = widths[(c as u8 - b'a') as usize];
            if cur + w > 100 {
                lines += 1; cur = w;
            } else {
                cur += w;
            }
        }
        vec![lines, cur]
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

class Solution {
    numberOfLines(widths: number[], s: string): number[] {
        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];
    }
}

Complexity

  • ⏰ Time complexity: O(n), where n is the length of s.
  • 🧺 Space complexity: O(1).