algoadvance

Leetcode 806. Number of Lines To Write String

Problem Statement

You are given a string s of lowercase English letters and an array widths, where widths[0] represents the width of the character 'a', widths[1] represents the width of the character 'b', and so on. Describe how many lines have been written and the width used in the last line given.

The paper has a set width of 100 units, and strings are written from left to right on the paper without any spaces. Each substring fits as many words as possible without exceeding the width 100 units.

You need to output an array resulted with two integers:

• The first integer is the number of lines needed to write the string s.
• The second integer is the width used in the last line.

Clarifying Questions

1. Can the string be empty?
   • Assume the string s will not be empty.
2. Will the array widths always have exactly 26 elements?
   • Yes, assume the widths array always has 26 elements.
3. What should happen if a single character’s width exceeds 100 units?
   • Since the input guarantees that it’s a lowercase English letter and the problem description does not specify this edge case, assume no single character will exceed 100 units in width.

Strategy

1. Initialize lines to 1 because at least one line will be required to start writing.
2. Initialize current_width to 0 as nothing has been written yet.
3. Iterate over each character in the string s:
   • Calculate the width of the current character from the widths array.
   • Check if adding this character’s width to current_width exceeds 100 units:
     • If it does, increment lines by 1 and reset current_width to the width of the current character.
     • If it does not, add the character’s width to current_width.
4. Return the number of lines and the width of the last line as an array of two integers.

Code

#include <vector>
#include <string>

std::vector<int> numberOfLines(std::vector<int>& widths, std::string s) {
    int lines = 1;
    int current_width = 0;
    
    for (char c : s) {
        int width = widths[c - 'a'];
        if (current_width + width > 100) {
            lines++;
            current_width = width;
        } else {
            current_width += width;
        }
    }
    
    return {lines, current_width};
}

Time Complexity

• O(n) where n is the length of the string s:
  • We iterate through each character in the string exactly once, making a constant time lookup in the widths array and performing constant-time arithmetic operations. Hence the time complexity is linear in relation to the length of the string s.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?