Sponsored
Sponsored
In this approach, we iterate over the string and keep track of the width of the current line. When adding another character exceeds the allowed line width of 100 pixels, we start a new line. We store the total number of lines and the width of the last line.
The time complexity of this approach is O(n), where s
. The space complexity is O(1), as we are only using a fixed amount of extra space.
We start by initializing totalLines
to 1 and currentWidth
to 0. As we iterate through each character in the string s
, we fetch its corresponding width from the widths
array. If adding a character would make the current line exceed 100 pixels, we increment the totalLines
and reset currentWidth
. Otherwise, we add the character's width to currentWidth
.
This approach takes the prefix summed widths of the string. For each new position, the difference between the prefix sums represents the total width of characters up to that position. Using this information, we determine how many characters fit into each line under the given constraints, thereby expanding calculation efficiency.
The time complexity is O(n) for constructing the prefix sum and iterating through it. The space complexity is O(n) due to the prefix sum array.
1using System;
2
3public class Solution {
4 public static int[] NumberOfLines(int[] widths, string s) {
5 int totalLines = 1;
6 int[] prefixSum = new int[s.Length + 1];
7
8 for (int i = 0; i < s.Length; ++i) {
9 prefixSum[i + 1] = prefixSum[i] + widths[s[i] - 'a'];
10 }
11
12 int lastValid = 0;
13
14 for (int i = 1; i <= s.Length; ++i) {
15 if (prefixSum[i] - prefixSum[lastValid] > 100) {
16 totalLines++;
17 lastValid = i - 1;
18 }
19 }
20
21 int lastWidth = prefixSum[s.Length] - prefixSum[lastValid];
22 return new int[] { totalLines, lastWidth };
23 }
24
25 public static void Main(string[] args) {
26 int[] widths = new int[]{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};
27 string s = "bbbcccdddaaa";
28 int[] result = NumberOfLines(widths, s);
29 Console.WriteLine($"[{result[0]}, {result[1]}]");
30 }
31}
32
C# follows the same structural format for computing cumulative prefix widths, proceeding to compare differential pixel sums against the 100-pixel benchmark. When this threshold is surpassed, line count increases and the lastValid
index is reset to denote new line initiations.