Number Of Lines To Write String - Leetcode Solution

Problem Statement:

You are given a string s of lowercase English letters and an array widths, where widths[0] is the width of 'a', widths[1] is the width of 'b', ..., and widths[25] is the width of 'z'.

We will write the string s over a set of infinite lines. In the first line, we write the substring of s from index 0 to index widths[0] - 1. In the second line, we write the substring of s from index widths[0] to index widths[0] + widths[1] - 1. And so on, until we finish writing the entire string.

Return an array result of length 2 where:

result[0] is the number of complete lines we have written. result[1] is the width used by the last line. Return result = [x, y] where x is the number of lines that we wrote, and y is the width of the last line.

Solution:

The solution to this problem is straightforward. We need to keep track of the number of lines required to write the given string s. We can do this by iterating over the string s, and for each character c in s, we can calculate its width using the given array widths and add it to the current line width.

Once the current line width exceeds 100, we increment the line count and reset the current line width to the width of the current character c. Finally, we return the line count and the current line width as the result.

Algorithm:

1. Initialize variables line_count and current_width to 1 and 0, respectively.
2. Iterate over each character c in the input string s.
3. Calculate the width of the current character c using the given array widths and add it to the current line width.
4. If the current line width exceeds 100, increment the line count and reset the current line width to the width of the current character c.
5. Return an array containing line_count and current_width.

Pseudocode:

function numberOfLines(widths: number[], s: string): number[] {
    let line_count = 1
    let current_width = 0
    
    for (const char of s) {
        const char_width = widths[char.charCodeAt(0) - 'a'.charCodeAt(0)]
        current_width += char_width
        
        if (current_width > 100) {
            line_count += 1
            current_width = char_width
        }
    }
    
    return [line_count, current_width]
}

Time Complexity:

The time complexity of the algorithm is O(n), where n is the length of the input string s. We iterate over each character of the input string s only once.

Space Complexity:

The space complexity of the algorithm is O(1). We use only a constant amount of memory to store the current line count and width, and the given array widths.

1