# Number of Lines To Write String
**Difficulty:** EASY
[External](https://leetcode.com/problems/number-of-lines-to-write-string)
Canonical: https://scaleengineer.com/dsa/problems/number-of-lines-to-write-string
**Data structures:** Array, String
---
## 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 than** `100` **pixels**. 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 array_ `result` _of length 2 where:_

* `result[0]` _is the total number of lines._
* `result[1]` _is the width of the last line in pixels._

**Example 1:**

**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:**

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

# Approaches
## Greedy Single-Pass Simulation
The problem can be solved efficiently using a single pass through the input string. This approach simulates the process of writing the string character by character, line by line, according to the given rules. We maintain a count of the lines used and the width of the current line. For each character, we check if it fits on the current line. If it does, we add its width to the current line's width. If not, we start a new line and place the character there.
**Time:** O(N), where N is the length of the string `s`. We perform a single pass through the string, and each operation inside the loop (array lookup, arithmetic, comparison) takes constant time. · **Space:** O(1), because we only use a few variables to store the line count and current width. The space required is constant and does not depend on the size of the input string `s`.
**Pros:** It is the most efficient solution with optimal time and space complexity.; The logic is straightforward and directly models the problem statement.; The implementation is simple and easy to understand.
**Cons:** There are no significant disadvantages to this approach as it is optimal in terms of both time and space complexity.
### Explanation
This approach is a greedy simulation. We iterate through the string `s` once, keeping track of the number of lines used and the pixel width of the current line. We start with one line and zero width. For each character in `s`, we find its width from the `widths` array. We then check if adding this character's width to the current line's width would exceed the maximum allowed width of 100 pixels. If it would, we increment our line count and set the current line's width to be the width of the current character (as it's the first character on the new line). If it fits, we simply add the character's width to the current line's width. After processing all characters, the total number of lines and the width of the very last line are our result.

```java
class Solution {
    public int[] numberOfLines(int[] widths, String s) {
        // The maximum width of a line.
        final int MAX_WIDTH = 100;

        // Start with one line.
        int lines = 1;
        // The width of the current line being written.
        int currentWidth = 0;

        // Iterate over each character in the string.
        for (char c : s.toCharArray()) {
            // Get the width of the current character.
            int charWidth = widths[c - 'a'];

            // Check if the character fits on the current line.
            if (currentWidth + charWidth > MAX_WIDTH) {
                // If not, start a new line.
                lines++;
                // The new line's width starts with the current character's width.
                currentWidth = charWidth;
            } else {
                // If it fits, add its width to the current line.
                currentWidth += charWidth;
            }
        }

        // Return the total number of lines and the width of the last line.
        return new int[]{lines, currentWidth};
    }
}
```
### Algorithm
*   Initialize `lines` to 1, as we always start with at least one line.
*   Initialize `currentWidth` to 0.
*   Define a constant `MAX_WIDTH` as 100.
*   Iterate through each character `c` of the input string `s`.
*   For each character, determine its width by looking it up in the `widths` array: `charWidth = widths[c - 'a']`.
*   Check if adding this character to the current line would exceed the `MAX_WIDTH`.
    *   If `currentWidth + charWidth > MAX_WIDTH`, it means the character must go on a new line. Increment `lines` and reset `currentWidth` to `charWidth`.
    *   Otherwise, the character fits. Add its width to the `currentWidth`: `currentWidth += charWidth`.
*   After iterating through all characters, the final values of `lines` and `currentWidth` are the answer.
*   Return an array containing `[lines, currentWidth]`.

# Solutions
### Java

```java
class Solution { private static final int MAX_WIDTH = 100 ; public int [] numberOfLines ( int [] widths , String s ) { int last = 0 , row = 1 ; for ( char c : s . toCharArray ()) { int w = widths [ c - 'a' ]; if ( last + w <= MAX_WIDTH ) { last += w ; } else { ++ row ; last = w ; } } return new int [] { row , last }; } }
```

### CPP

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

```

### Python

```python
class Solution:
    def numberOfLines(self, widths: List[int], s: str) -> List[int]: last, row = 0, 1 for c in s: w = widths[ord(c) - ord('a')] if last + w <= 100: last += w else: row += 1 last = w return [row, last]

```