Number of Lines To Write String

Easy

Asked by:

11 views

Topics:

ArraysStrings

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

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

Are the widths in the `widths` array always positive integers? What are the minimum and maximum possible values for each width?
Is the input string `s` guaranteed to only contain lowercase English letters?
What is the range for the length of the input string `s`?
If the string `s` requires exactly 100 pixels on the last line, do I still need to start a new line?
If the input string `s` is empty, what should the function return?

Brute Force Solution

Approach

The brute force approach involves testing every possible combination of words on each line to find a valid arrangement. It exhaustively explores all ways to split the given text into lines that meet the maximum line width. We continue until we've considered all possible line arrangements.

Here's how the algorithm would work step-by-step:

Start by trying to put the first word on a line.
See if the first and second words together fit on a line. Then the first, second, and third words, and so on.
If at some point, adding the next word makes the line too long, stop adding words to that line.
Start a new line with the overflowing word.
Repeat this process, trying every possible combination of words on each line until all words are placed.
Count the number of lines used in this arrangement.
Do this whole process again, but this time start by putting only the first two words on the first line, then the first three, and so on, trying every other starting point.
Repeat until we've tested every possible way to start the first line.
Of all the arrangements that meet the maximum line length requirement, find the one that uses the fewest number of lines.

Code Implementation

def number_of_lines_brute_force(
    widths,
    text,
    max_width
):

    words = text.split()
    minimum_lines = float('inf')

    for start_index in range(len(words)):
        number_of_lines = 0
        current_line_width = 0
        word_index = start_index
        
        # Iterate to build lines.
        while word_index < len(words):
            number_of_lines += 1
            current_line_width = 0

            while word_index < len(words):
                word_width = widths[ord(words[word_index]) - ord('a')]
                
                # Check if adding the next word exceeds max width
                if current_line_width + word_width > max_width:
                    break
                
                current_line_width += word_width
                
                word_index += 1

        minimum_lines = min(minimum_lines, number_of_lines)

    return minimum_lines

Big(O) Analysis

Time Complexity

O(2^n) – The brute force approach explores every possible combination of words on each line. For each word, we have the choice to either include it on the current line or start a new line. Since there are n words, this leads to 2^n possible arrangements of lines. The cost is driven by trying out all possible line breaks between words to minimize the total number of lines. Therefore, the time complexity is O(2^n).

Space Complexity

O(1) – The provided brute force approach explores different combinations of words on each line, but it doesn't explicitly mention storing all these combinations simultaneously. The algorithm seems to recalculate the number of lines for each arrangement on-the-fly. It might use a few integer variables to keep track of the current line length, the number of lines used so far, and potentially a variable to store the minimum number of lines found. These variables consume constant space regardless of the input size N (where N is the number of words), therefore the auxiliary space complexity is O(1).

Optimal Solution

Approach

The challenge is to determine how many lines are needed to write a string given a specific width for each character. The optimal approach is to iterate through the string, character by character, and keep track of the current line's used width. When the line is full, increment the line count and start a new line.

Here's how the algorithm would work step-by-step:

Begin with the first character and an empty line.
Check the width of the current character.
If adding the character's width to the current line's width does not exceed the line width limit, add the character to the current line and increase the current line's width.
If adding the character's width exceeds the limit, then start a new line. Increment the line count and set the new line's width to be the width of the current character.
Continue this process for each character in the string.
After processing all characters, the line count will represent the total number of lines needed.
Also, the current line's width will represent how much width was used in the last line.

Code Implementation

def number_of_lines(widths, string_to_write):
    line_count = 1
    current_line_width = 0

    for character in string_to_write:
        character_index = ord(character) - ord('a')
        character_width = widths[character_index]

        # Check if adding the character exceeds the line limit.
        if current_line_width + character_width > 100:
            line_count += 1

            # Start a new line with the current character's width.
            current_line_width = character_width

        else:
            # Add the character's width to the current line.
            current_line_width += character_width

    return [line_count, current_line_width]

Big(O) Analysis

Time Complexity

O(n) – The time complexity is determined by iterating through the input string once. The input size 'n' represents the length of the string. For each of the 'n' characters in the string, a constant number of operations (width lookup, addition, and comparison) are performed. Thus, the total number of operations scales linearly with the length of the string, resulting in a time complexity of O(n).

Space Complexity

O(1) – The algorithm iterates through the input string without creating any auxiliary data structures that scale with the string's length. It uses a fixed number of variables to store the current line's width and the number of lines. The space required for these variables remains constant irrespective of the input string's size (N). Therefore, the space complexity is O(1).

Edge Cases

Case	How to Handle
Null or empty input widths array	Return [0, 0] indicating 0 lines and 0 pixels used on the last line, as there is nothing to write.
Input string S is null or empty	Return [0, 0] indicating 0 lines and 0 pixels used on the last line, as there is nothing to write.
All characters in S require maximum width (e.g., all 'w')	Handle line wrapping correctly; ensure line count increments when exceeding 100 pixels.
All characters in S require minimum width (e.g., all 'a')	Multiple characters will fit on each line, correctly incrementing character count and line count only when needed.
Widths array contains a zero value	The problem statement specifies widths[i] to be non-zero, and any input violating this constraint means the input is malformed and an exception should be thrown or a designated error value returned.
Input string 'S' contains characters not present in the widths array (e.g., extended ASCII or Unicode)	Throw an IllegalArgumentException, return a designated error value like [-1, -1], or handle gracefully by skipping those characters if within a defined subset.
The String 'S' is extremely long (close to Integer.MAX_VALUE characters)	Handle potential integer overflow when calculating pixel usage, especially if character widths are large; consider using long to store the total pixels.
Widths array contains extremely large values (approaching Integer.MAX_VALUE), but the total pixels do not exceed Integer.MAX_VALUE due to short string length	Ensure intermediate pixel calculations don't overflow before final checks with the widths array.

Null or empty input widths array

How to Handle:

Return [0, 0] indicating 0 lines and 0 pixels used on the last line, as there is nothing to write.

Input string S is null or empty

How to Handle:

Return [0, 0] indicating 0 lines and 0 pixels used on the last line, as there is nothing to write.

All characters in S require maximum width (e.g., all 'w')

How to Handle:

Handle line wrapping correctly; ensure line count increments when exceeding 100 pixels.

All characters in S require minimum width (e.g., all 'a')

How to Handle:

Multiple characters will fit on each line, correctly incrementing character count and line count only when needed.

Widths array contains a zero value

How to Handle:

The problem statement specifies widths[i] to be non-zero, and any input violating this constraint means the input is malformed and an exception should be thrown or a designated error value returned.

Input string 'S' contains characters not present in the widths array (e.g., extended ASCII or Unicode)

How to Handle:

Throw an IllegalArgumentException, return a designated error value like [-1, -1], or handle gracefully by skipping those characters if within a defined subset.

The String 'S' is extremely long (close to Integer.MAX_VALUE characters)

How to Handle:

Handle potential integer overflow when calculating pixel usage, especially if character widths are large; consider using long to store the total pixels.

Widths array contains extremely large values (approaching Integer.MAX_VALUE), but the total pixels do not exceed Integer.MAX_VALUE due to short string length

How to Handle:

Ensure intermediate pixel calculations don't overflow before final checks with the widths array.