algoadvance

Leetcode 806. Number of Lines To Write String

Problem Statement

You are given a list widths, where widths[0] is the width of ‘a’, widths[1] is the width of ‘b’, …, and widths[25] is the width of ‘z’. Given a string s, write it onto several lines such that each line has a maximum width of 100 units. You should pack your words in a greedy manner; that is, you want to pack as many words as possible in each line. Return an array result of length 2 where:

Example:

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:
All letters have the same length of 10. To write all 26 letters,
we need two full lines (each with 100 units) and one line with 60 units.

Clarifying Questions

  1. Are all characters in the string lowercase?
    • Yes, the string s consists only of lowercase English letters.
  2. Should we consider any special or fringe cases in the string that might have non-alphabetic characters?
    • No, s will contain only characters from ‘a’ to ‘z’.
  3. Can the input string be empty?
    • Yes, an empty string is a valid input. In that case, the result should be [0, 0].

Strategy

  1. Initialize lines to 1 because there’s at least one line if the string is not empty.
  2. Initialize current_width to 0 to keep track of the current line width.
  3. Iterate over each character in the input string s:
    • Compute the width of the current character using the widths array.
    • If adding this character exceeds 100 units:
      • Increment the lines count.
      • Reset current_width to the width of the current character.
    • Otherwise, add the character’s width to current_width.
  4. Return the total lines and current_width (width of the last line).

Time Complexity

The time complexity of this solution is O(n), where n is the length of the input string s. We iterate through the string once, and all other operations (such as accessing the widths array) are O(1).

public class Solution {
    public int[] numberOfLines(int[] widths, String s) {
        int lines = 1;
        int currentWidth = 0;
        
        for (char c : s.toCharArray()) {
            int width = widths[c - 'a'];
            
            if (currentWidth + width > 100) {
                lines++;
                currentWidth = width;
            } else {
                currentWidth += width;
            }
        }
        
        return new int[]{lines, currentWidth};
    }
}

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