We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Number of Lines To Write String

Number: 824

Difficulty: Easy

Paid? No

Companies: Google

Problem Description

Given a string s and an array widths where widths[i] represents the pixel width of the letter corresponding to the (i + 'a'), the task is to write the string s on multiple lines such that each line does not exceed 100 pixels. The process starts from the beginning of s and continues line by line. The goal is to determine the total number of lines used as well as the width in pixels used by the last line.

Key Insights

  • Map each character in s to its pixel width using the widths array.
  • Simulate the process of writing on each line, keeping a running total of the current line’s pixel width.
  • When adding the next character would exceed 100 pixels, increment the line count and reset the current line width.
  • Iterate through the string in a single pass.

Space and Time Complexity

Time Complexity: O(n), where n is the length of s.
Space Complexity: O(1), only constant extra space is used.

Solution

The solution involves iterating over each character in the string and continuously adding its corresponding width (from the widths array) to a running sum representing the current line's width. When the running sum plus a new character's width exceeds 100, it indicates that a new line must be started. In this case, the line count is incremented and the running sum is reset to start with the new character. This method uses simple arithmetic and conditional checks to correctly simulate the procedure, resulting in a straightforward and efficient solution.

Code Solutions

# Function to calculate the number of lines and width of the last line
def numberOfLines(widths, s):
    # Start with the first line and a current width of 0
    lines = 1
    current_width = 0
    # Process each character in the string
    for char in s:
        # Calculate the width of the current character
        char_width = widths[ord(char) - ord('a')]
        # If adding the current character exceeds 100 pixels, start a new line
        if current_width + char_width > 100:
            lines += 1
            current_width = 0
        # Add the character's width to the current line
        current_width += char_width
    # Return the total number of lines and the last line width
    return [lines, current_width]

# Example usage:
widths = [10] * 26
s = "abcdefghijklmnopqrstuvwxyz"
print(numberOfLines(widths, s))
← Back to All Questions