Number of Lines To Write String — Problem & Solution
Number of Lines To Write String solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. An easy problem.
Number of Lines To Write String is an easy coding problem on arrays, strings and simulation, asked in Adobe, TCS and Infosys interviews.
- Difficulty: Easy
- Topics: Arrays, Strings, Simulation
- Asked at: Adobe, TCS, Infosys
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
You are writing s across lines that are at most 100 units wide. widths[0] is the width of 'a', widths[1] of 'b', and so on.
Write the characters in order, moving to a new line whenever the next character would push the current line past 100 units. Return [numberOfLines, widthOfLastLine].
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: Ten characters fill a line exactly; the third line holds the last six.
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: The narrow a lets eleven characters fit on the first line.
Example 3
Input: widths = [5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5], s = "ab"
Output: [1,10]
Constraints
widths.length == 262 <= widths[i] <= 101 <= s.length <= 1000s consists of lowercase English letters.
Hints for Number of Lines To Write String
Hint 1
Simulate: carry the width used on the current line.
Hint 2
Break before adding a character that would overflow, not after.
Hint 3
The answer's second component is whatever is left on the final line.
How to solve Number of Lines To Write String
Straight simulation. The only decision per character is whether it still fits, and that decision must be made before the character is placed.
Approach
- Start on line 1 with 0 units used.
- For each character, look up its width. If
used + width > 100, start a new line with 0 used. - Add the width to
used. - Return
[lines, used].
Why it works
Greedy placement is forced — the statement gives no choice about where characters go, so the simulation is the definition.
Complexity
- Time —
O(n) - Space —
O(1)
Pitfalls
- Adding the width first and then checking for overflow miscounts the line the character lands on.
- Using
>= 100breaks a line that is exactly full, which is still legal. - Starting the line counter at 0 undercounts by one for any non-empty string.
Reference solution
Python
from typing import List
def numberOfLines(widths: List[int], s: str) -> List[int]:
lines, used = 1, 0
for c in s:
w = widths[ord(c) - 97]
if used + w > 100:
lines += 1
used = 0
used += w
return [lines, used]Java
public static int[] numberOfLines(int[] widths, String s) {
int lines = 1, used = 0;
for (int i = 0; i < s.length(); i++) {
int w = widths[s.charAt(i) - 'a'];
if (used + w > 100) { lines++; used = 0; }
used += w;
}
return new int[] { lines, used };
}C++
vector<int> numberOfLines(vector<int>& widths, string s) {
int lines = 1, used = 0;
for (char c : s) {
int w = widths[c - 'a'];
if (used + w > 100) { lines++; used = 0; }
used += w;
}
return { lines, used };
}JavaScript
var numberOfLines = function(widths, s) {
var lines = 1, used = 0;
for (var i = 0; i < s.length; i++) {
var w = widths[s.charCodeAt(i) - 97];
if (used + w > 100) { lines++; used = 0; }
used += w;
}
return [lines, used];
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.