Algorithm


Problem Name: 806. Number of Lines To Write String

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.
 

Code Examples

#1 Code Example with C++ Programming

Code - C++ Programming


class Solution {
public:
    vector<int> numberOfLines(vector<int>& widths, string S) {
        int line = 1, sum = 0;
        for(char c: S){
            sum += widths[c - 'a'];
            if(sum > 100) sum = widths[c - 'a'], line++;
        }
        return {line, sum};
    }
};
Copy The Code & Try With Live Editor

Input

x
+
cmd
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

x
+
cmd
[3,60]

#2 Code Example with Java Programming

Code - Java Programming


class Solution {
  public int[] numberOfLines(int[] widths, String S) {
    int numOfLines = 1;
    int currWidth = 0;
    for (char c : S.toCharArray()) {
      int width = widths[c - 'a'];
      currWidth += width;
      if (currWidth > 100) {
        numOfLines++;
        currWidth = width;
      }
    }
    return new int[]{numOfLines, currWidth};
  }
}
Copy The Code & Try With Live Editor

Input

x
+
cmd
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

x
+
cmd
[3,60]

#3 Code Example with Python Programming

Code - Python Programming


class Solution(object):
    def numberOfLines(self, widths, S):
        """
        :type widths: List[int]
        :type S: str
        :rtype: List[int]
        """
        left=0
        lines=1
        for char in S:
            if left+widths[ord(char)-ord("a")]<=100:
                left+=widths[ord(char)-ord("a")]
            else:
                lines+=1
                left=widths[ord(char)-ord("a")]
        return [lines, left]
Copy The Code & Try With Live Editor

Input

x
+
cmd
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

x
+
cmd
[2,4]

#4 Code Example with C# Programming

Code - C# Programming


namespace LeetCode
{
    public class _0806_NumberOfLinesToWriteString
    {
        public int[] NumberOfLines(int[] widths, string S)
        {
            var lines = 1;
            var width = 0;
            foreach (var ch in S)
            {
                width += widths[ch - 'a'];

                if (width > 100)
                {
                    lines++;
                    width = widths[ch - 'a'];
                }
            }

            return new int[] { lines, width };
        }
    }
}
Copy The Code & Try With Live Editor

Input

x
+
cmd
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

x
+
cmd
[2,4]
Advertisements

Demonstration


Previous
#805 Leetcode Split Array With Same Average Solution in C, C++, Java, JavaScript, Python, C# Leetcode
Next
#807 Leetcode Max Increase to Keep City Skyline Solution in C, C++, Java, JavaScript, Python, C# Leetcode