Number of Lines To Write String - Solution & Explanation
Problem Statement
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 == 262 <= widths[i] <= 101 <= s.length <= 1000scontains only lowercase English letters.
Approach Overview
Problem Overview: You are given an array widths where each element represents the pixel width of characters 'a' to 'z'. A string s must be written on lines with a maximum width of 100 pixels. As you place characters sequentially, once the current line exceeds the limit, you move to a new line. The task is to return the number of lines used and the width occupied by the last line.
Approach 1: Greedy Approach (O(n) time, O(1) space)
This problem naturally fits a greedy simulation. Iterate through the string once and keep a running sum representing the width used in the current line. For each character, convert it to an index using c - 'a' and fetch its width from the array. If adding this width would exceed 100, start a new line and reset the current width to that character's width. Otherwise, keep accumulating. The greedy choice works because each character must appear in order and the only decision is whether it fits in the current line or forces a new one. This linear scan makes the solution O(n) time with O(1) extra space since only counters are maintained. The logic relies on simple iteration over a string with values stored in an array.
Approach 2: Prefix Sum Approach (O(n) time, O(n) space)
A prefix sum variant first converts each character of s into its width and stores cumulative widths in a prefix array. The prefix sum at position i represents the total width of the first i characters. While scanning this structure, track when the difference between two prefix indices exceeds 100. That boundary indicates the start of a new line. This technique separates width computation from line segmentation and can help when the widths are reused or analyzed further. Building the prefix array costs O(n) time and O(n) space, and the subsequent scan is also linear.
Recommended for interviews: The greedy simulation is the expected answer. It demonstrates that you can translate constraints directly into a linear pass and maintain minimal state. Interviewers typically want to see the simple currentWidth + charWidth > 100 check and line counter update. The prefix sum variant shows familiarity with the prefix sum technique but introduces unnecessary memory for this problem.
Approach 1: Greedy Approach
In this approach, we iterate over the string and keep track of the width of the current line. When adding another character exceeds the allowed line width of 100 pixels, we start a new line. We store the total number of lines and the width of the last line.
We start by initializing totalLines to 1 and currentWidth to 0. As we iterate through each character in the string s, we fetch its corresponding width from the widths array. If adding a character would make the current line exceed 100 pixels, we increment the totalLines and reset currentWidth. Otherwise, we add the character's width to currentWidth.
Complexity
The time complexity of this approach is O(n), where s. The space complexity is O(1), as we are only using a fixed amount of extra space.
Approach 2: Prefix Sum Approach
This approach takes the prefix summed widths of the string. For each new position, the difference between the prefix sums represents the total width of characters up to that position. Using this information, we determine how many characters fit into each line under the given constraints, thereby expanding calculation efficiency.
In this solution, we first compute a prefix sum array where prefixSum[i] contains the total width of the first i characters. We then iterate through the prefix sum to determine where the line widths exceed 100, marking new line starts and updating currentWidth.
Complexity
The time complexity is O(n) for constructing the prefix sum and iterating through it. The space complexity is O(n) due to the prefix sum array.
Approach 3: Simulation
We define two variables lines and last, representing the number of lines and the width of the last line, respectively. Initially, lines = 1 and last = 0.
We iterate through the string s. For each character c, we calculate its width w. If last + w leq 100, we add w to last. Otherwise, we increment lines by one and reset last to w.
Finally, we return an array consisting of lines and last.
The time complexity is O(n), where n is the length of the string s. The space complexity is O(1).
Complexity Comparison
| Approach | Complexity |
|---|---|
| Greedy Approach | The time complexity of this approach is O(n), where |
| Prefix Sum Approach | The time complexity is O(n) for constructing the prefix sum and iterating through it. The space complexity is O(n) due to the prefix sum array. |
| Simulation | — |
Detailed Complexity Analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Greedy Simulation | O(n) | O(1) | Best general solution. Simple single pass through the string with constant memory. |
| Prefix Sum | O(n) | O(n) | Useful when cumulative widths are needed for additional analysis or repeated queries. |
Video Solution
LeetCode Number of Lines To Write String Solution Explained - Java • Nick White • 3,948 views views
Watch 9 more video solutions →Frequently Asked Questions
Is Number of Lines To Write String easy or hard?
Number of Lines To Write String Python/Java solution
How to solve Number of Lines To Write String in O(n)?
What is the best approach for Number of Lines To Write String?
Is Number of Lines To Write String asked at Google/Amazon/Meta?
What data structure is used in Number of Lines To Write String?
What is the time complexity of Number of Lines To Write String?
Ready to solve this problem?
Practice Number of Lines To Write String with our built-in code editor and test cases.
Practice on FleetCodeTable of Contents
Practice this problem
Open in Editor