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.
JavaScript uses the charCodeAt method to find each character's integer representation, thus mapping it to the widths array. The function emulates a greedy approach by updating totalLines when line width is exceeded with an additional character.
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.
1function numberOfLines(widths, s) {
2 let totalLines = 1;
3 let prefixSum = new Array(s.length + 1).fill(0);
4
5 for (let i = 0; i < s.length; ++i) {
6 prefixSum[i + 1] = prefixSum[i] + widths[s.charCodeAt(i) - 'a'.charCodeAt(0)];
7 }
8
9 let lastValid = 0;
10 for (let i = 1; i <= s.length; ++i) {
11 if (prefixSum[i] - prefixSum[lastValid] > 100) {
12 totalLines++;
13 lastValid = i - 1;
14 }
15 }
16
17 let lastWidth = prefixSum[s.length] - prefixSum[lastValid];
18 return [totalLines, lastWidth];
19}
20
21// Example usage
22const 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];
23const s = "bbbcccdddaaa";
24console.log(numberOfLines(widths, s));
25JavaScript uses prefixSum computations to track cumulative character widths, determining when they surpass the line width threshold. With each instance of overflow, we adjust the start point for subsequent line measurement.