Number of Lines To Write String solution and explanation
Google
9 more videos on this problem
LeetCode Number of Lines To Write String Solution Explained - JavaNick White · 5:39 · 3K views
Number of Lines To Write String | LeetCode 806 WalkthroughJacob Broughton · 7:58 · 734 views
806. Number of Lines To Write String || LEETCODE SOLUTION || IN C++ || DATA STRUCTURE AND ALGORITHMAbhishweta Gupta · 2:30 · 697 views
806. Number of Lines To Write String | Leetcode | PythonAbdullah Arshed · 3:54 · 526 views
Leetcode solving: 806 Number of Lines To Write StringMath Geeks · 4:05 · 297 views
LeetCode 806 | Number of Lines To Write String | JavaSleepy Cracker · 2:39 · 184 views
Number of Lines To Write String | JAVAKnowledge Amplifier · 3:40 · 124 views
my attempt at solving leetcode 806: number of lines to write string [SOLVED]Cameron Late · 18:14 · 92 views
806. Number of Lines To Write String - Javascript - Time: O(n) Space: O(1) - LeetcodeAaron Sadino Coding · 0:47 · 62 views
No Sound Leetcode 806: Number of Lines To Write StringExtremeProgrammer · 1:39 · 14 views
The 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 == 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.
def numberOfLines(widths, s):
total_lines = 1
current_width = 0
for c in s:
char_width = widths[ord(c) - ord('a')]
if current_width + char_width > 100:
total_lines += 1
current_width = char_width
else:
current_width += char_width
return [total_lines, current_width]
# Example Usage
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"
print(numberOfLines(widths, s))import java.util.List;
import java.util.ArrayList;
public class Solution {
public static int[] numberOfLines(int[] widths, String s) {
int totalLines = 1;
int currentWidth = 0;
for (char c : s.toCharArray()) {
int charWidth = widths[c - 'a'];
if (currentWidth + charWidth > 100) {
totalLines++;
currentWidth = charWidth;
} else {
currentWidth += charWidth;
}
}
return new int[]{totalLines, currentWidth};
}
public static void main(String[] args) {
int[] 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};
String s = "bbbcccdddaaa";
int[] result = numberOfLines(widths, s);
System.out.printf("[%d, %d]\n", result[0], result[1]);
}
}#include <vector>
#include <string>
#include <iostream>
using namespace std;
vector<int> numberOfLines(vector<int>& widths, string s) {
int totalLines = 1;
int currentWidth = 0;
for (char c : s) {
int charWidth = widths[c - 'a'];
if (currentWidth + charWidth > 100) {
totalLines++;
currentWidth = charWidth;
} else {
currentWidth += charWidth;
}
}
return {totalLines, currentWidth};
}
int main() {
vector<int> 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};
string s = "bbbcccdddaaa";
vector<int> result = numberOfLines(widths, s);
cout << "[" << result[0] << ", " << result[1] << "]" << endl;
return 0;
}function numberOfLines(widths, s) {
let totalLines = 1;
let currentWidth = 0;
for (let i = 0; i < s.length; i++) {
let charWidth = widths[s.charCodeAt(i) - 'a'.charCodeAt(0)];
if (currentWidth + charWidth > 100) {
totalLines++;
currentWidth = charWidth;
} else {
currentWidth += charWidth;
}
}
return [totalLines, currentWidth];
}
// Example usage
const 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];
const s = "bbbcccdddaaa";
console.log(numberOfLines(widths, s));#include <stdio.h>
void numberOfLines(int* widths, int widthsSize, char* s, int* result) {
int currentWidth = 0;
int totalLines = 1; // Start with the first line
for (int i = 0; s[i] != '\0'; ++i) {
int charWidth = widths[s[i] - 'a'];
if (currentWidth + charWidth > 100) {
totalLines++;
currentWidth = 0;
}
currentWidth += charWidth;
}
result[0] = totalLines;
result[1] = currentWidth;
}
int main() {
int widths[26] = {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};
char s[] = "bbbcccdddaaa";
int result[2];
numberOfLines(widths, 26, s, result);
printf("[%d, %d]\n", result[0], result[1]);
return 0;
}using System;
public class Solution {
public static int[] NumberOfLines(int[] widths, string s) {
int totalLines = 1;
int currentWidth = 0;
foreach (char c in s) {
int charWidth = widths[c - 'a'];
if (currentWidth + charWidth > 100) {
totalLines++;
currentWidth = charWidth;
} else {
currentWidth += charWidth;
}
}
return new int[] { totalLines, currentWidth };
}
public static void Main(string[] args) {
int[] widths = new int[]{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};
string s = "bbbcccdddaaa";
int[] result = NumberOfLines(widths, s);
Console.WriteLine($"[{result[0]}, {result[1]}]");
}
}For Python, the function calculates each character's width using its ASCII value and the provided widths list. It updates total_lines and current_width similarly to other solutions upon encountering a character that doesn't fit within the current line.
The time complexity is O(n), where is the length of the string s. The space complexity is O(1).
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.
def numberOfLines(widths, s):
total_lines = 1
prefix_sum = [0] * (len(s) + 1)
for i in range(len(s)):
prefix_sum[i + 1] = prefix_sum[i] + widths[ord(s[i]) - ord('a')]
last_valid = 0
for i in range(1, len(s) + 1):
if prefix_sum[i] - prefix_sum[last_valid] > 100:
total_lines += 1
last_valid = i - 1
last_width = prefix_sum[len(s)] - prefix_sum[last_valid]
return [total_lines, last_width]
# Example Usage
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"
print(numberOfLines(widths, s))import java.util.ArrayList;
import java.util.List;
public class Solution {
public static int[] numberOfLines(int[] widths, String s) {
int totalLines = 1;
int[] prefixSum = new int[s.length() + 1];
prefixSum[0] = 0;
for (int i = 0; i < s.length(); ++i) {
prefixSum[i + 1] = prefixSum[i] + widths[s.charAt(i) - 'a'];
}
int lastValid = 0;
for (int i = 1; i <= s.length(); ++i) {
if (prefixSum[i] - prefixSum[lastValid] > 100) {
totalLines++;
lastValid = i - 1;
}
}
return new int[]{totalLines, prefixSum[s.length()] - prefixSum[lastValid]};
}
public static void main(String[] args) {
int[] 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};
String s = "bbbcccdddaaa";
int[] result = numberOfLines(widths, s);
System.out.printf("[%d, %d]\n", result[0], result[1]);
}
}#include <iostream>
#include <vector>
using namespace std;
vector<int> numberOfLines(vector<int>& widths, string s) {
int totalLines = 1;
vector<int> prefixSum(s.size() + 1);
prefixSum[0] = 0;
for (int i = 0; i < s.size(); ++i) {
prefixSum[i + 1] = prefixSum[i] + widths[s[i] - 'a'];
}
int lastWidth = 0;
for (int i = 1; i <= s.size(); ++i) {
if (prefixSum[i] - prefixSum[lastWidth] > 100) {
totalLines++;
lastWidth = i - 1;
}
}
return {totalLines, prefixSum[s.size()] - prefixSum[lastWidth]};
}
int main() {
vector<int> 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};
string s = "bbbcccdddaaa";
vector<int> result = numberOfLines(widths, s);
cout << "[" << result[0] << ", " << result[1] << "]" << endl;
return 0;
}function numberOfLines(widths, s) {
let totalLines = 1;
let prefixSum = new Array(s.length + 1).fill(0);
for (let i = 0; i < s.length; ++i) {
prefixSum[i + 1] = prefixSum[i] + widths[s.charCodeAt(i) - 'a'.charCodeAt(0)];
}
let lastValid = 0;
for (let i = 1; i <= s.length; ++i) {
if (prefixSum[i] - prefixSum[lastValid] > 100) {
totalLines++;
lastValid = i - 1;
}
}
let lastWidth = prefixSum[s.length] - prefixSum[lastValid];
return [totalLines, lastWidth];
}
// Example usage
const 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];
const s = "bbbcccdddaaa";
console.log(numberOfLines(widths, s));#include <stdio.h>
#include <string.h>
void numberOfLines(int* widths, int widthsSize, char* s, int* result) {
int totalLines = 1, currentWidth = 0;
int prefixSum[strlen(s) + 1];
prefixSum[0] = 0;
for (int i = 0; s[i] != '\0'; ++i) {
prefixSum[i + 1] = prefixSum[i] + widths[s[i] - 'a'];
}
for (int i = 0; s[i] != '\0'; ++i) {
int nextWidth = prefixSum[i + 1] - prefixSum[currentWidth];
if (nextWidth > 100) {
totalLines++;
currentWidth = i;
}
}
result[0] = totalLines;
result[1] = prefixSum[strlen(s)] - prefixSum[currentWidth];
}
int main() {
int widths[26] = {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};
char s[] = "bbbcccdddaaa";
int result[2];
numberOfLines(widths, 26, s, result);
printf("[%d, %d]\n", result[0], result[1]);
return 0;
}using System;
public class Solution {
public static int[] NumberOfLines(int[] widths, string s) {
int totalLines = 1;
int[] prefixSum = new int[s.Length + 1];
for (int i = 0; i < s.Length; ++i) {
prefixSum[i + 1] = prefixSum[i] + widths[s[i] - 'a'];
}
int lastValid = 0;
for (int i = 1; i <= s.Length; ++i) {
if (prefixSum[i] - prefixSum[lastValid] > 100) {
totalLines++;
lastValid = i - 1;
}
}
int lastWidth = prefixSum[s.Length] - prefixSum[lastValid];
return new int[] { totalLines, lastWidth };
}
public static void Main(string[] args) {
int[] widths = new int[]{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};
string s = "bbbcccdddaaa";
int[] result = NumberOfLines(widths, s);
Console.WriteLine($"[{result[0]}, {result[1]}]");
}
}In Python, the prefix sum list is built and used to check when new lines should begin. The technique identifies when accumulated width measurements overstep the 100-pixel limit, thus dictating consecutive line increments for line counting accordingly.
The time complexity is O(n) for prefix summation. The space complexity is O(n) given the size of the prefix sum list.
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).
function numberOfLines(widths: number[], s: string): number[] {
let [lines, last] = [1, 0];
for (const c of s) {
const w = widths[c.charCodeAt(0) - 'a'.charCodeAt(0)];
if (last + w <= 100) {
last += w;
} else {
++lines;
last = w;
}
}
return [lines, last];
}func numberOfLines(widths []int, s string) []int {
lines, last := 1, 0
for _, c := range s {
w := widths[c-'a']
if last+w <= 100 {
last += w
} else {
lines++
last = w
}
}
return []int{lines, last}
}impl Solution {
pub fn number_of_lines(widths: Vec<i32>, s: String) -> Vec<i32> {
let mut lines = 1;
let mut last = 0;
for c in s.chars() {
let idx = ((c as u8) - b'a') as usize;
let w = widths[idx];
if last + w <= 100 {
last += w;
} else {
lines += 1;
last = w;
}
}
vec![lines, last]
}
}Complexity comparison
| Approach | Complexity |
|---|---|
| Greedy Approach | The time complexity is O(n), where is the length of the string |
| Prefix Sum Approach | The time complexity is O(n) for prefix summation. The space complexity is O(n) given the size of the prefix sum list. |
| Simulation | – |
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. |
Frequently asked questions
Is Number of Lines To Write String easy or hard?
LeetCode classifies this problem as Easy with an acceptance rate above 70%. The challenge is mainly careful simulation and handling the width reset correctly when a new line starts.
Number of Lines To Write String Python/Java solution
The implementation is straightforward in Python, Java, C++, or JavaScript. Map each character to its width using the index c - 'a', track the current line width, and increment the line count whenever the limit of 100 pixels is exceeded.
How to solve Number of Lines To Write String in O(n)?
Scan the string once and track the width used in the current line. For each character, look up its width from the 26‑element array. If currentWidth + charWidth exceeds 100, increment the line counter and reset the width to that character; otherwise continue accumulating.
What is the best approach for Number of Lines To Write String?
The greedy simulation is the best approach. Iterate through the string, keep a running width for the current line, and start a new line whenever adding the next character exceeds 100 pixels. This solution runs in O(n) time with O(1) extra space.
Is Number of Lines To Write String asked at Google/Amazon/Meta?
Problems of this style appear frequently in screening rounds at companies like Amazon and Google because they test careful simulation and edge‑case handling. The task evaluates whether candidates can translate constraints into a clean linear pass.
What data structure is used in Number of Lines To Write String?
The solution primarily uses an array for character widths and simple counters while iterating through the string. Some variations also use prefix sum arrays to store cumulative widths, though this is not required for the optimal solution.
What is the time complexity of Number of Lines To Write String?
The optimal solution runs in O(n) time where n is the length of the string. Each character is processed exactly once to check whether it fits in the current line or requires starting a new one. Space complexity is O(1).