Number of Lines To Write String

Easy
666.

Number of Lines To Write String

Number of Lines To Write String is an easy coding problem on arrays, strings and simulation, asked in Adobe, TCS and Infosys interviews.

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 == 26
  • 2 <= widths[i] <= 10
  • 1 <= s.length <= 1000
  • s consists of lowercase English letters.
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[]} widths
 * @param {string} s
 * @return {number[]}
 */
var numberOfLines = function(widths, s) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

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 == 26
  • 2 <= widths[i] <= 10
  • 1 <= s.length <= 1000
  • s consists of lowercase English letters.

Hints for Number of Lines To Write String

  1. Hint 1

    Simulate: carry the width used on the current line.

  2. Hint 2

    Break before adding a character that would overflow, not after.

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

  1. Start on line 1 with 0 units used.
  2. For each character, look up its width. If used + width > 100, start a new line with 0 used.
  3. Add the width to used.
  4. 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 >= 100 breaks 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.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays · Strings