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.
1#include <string>
#include <iostream>
using namespace std;
vector<int> numberOfLines(vector<int>& widths, string s) {
int totalLines = 1;
int currentWidth = 0;
for (char c : s) {
int charWidth = widths[c - 'a'];
if (currentWidth + charWidth > 100) {
totalLines++;
currentWidth = charWidth;
} else {
currentWidth += charWidth;
}
}
return {totalLines, currentWidth};
}
int main() {
vector<int> 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};
string s = "bbbcccdddaaa";
vector<int> result = numberOfLines(widths, s);
cout << "[" << result[0] << ", " << result[1] << "]" << endl;
return 0;
}
The C++ implementation similarly increments totalLines whenever adding the current character would exceed 100 pixels. The currentWidth is reset to the current character's width in such a case. The numberOfLines function returns a vector containing the total number of lines and the width of the last line.
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.
1#include <stdio.h>
2#include <string.h>
3
4void numberOfLines(int* widths, int widthsSize, char* s, int* result) {
5 int totalLines = 1, currentWidth = 0;
6 int prefixSum[strlen(s) + 1];
7 prefixSum[0] = 0;
8
9 for (int i = 0; s[i] != '\0'; ++i) {
10 prefixSum[i + 1] = prefixSum[i] + widths[s[i] - 'a'];
11 }
12
13 for (int i = 0; s[i] != '\0'; ++i) {
14 int nextWidth = prefixSum[i + 1] - prefixSum[currentWidth];
15 if (nextWidth > 100) {
16 totalLines++;
17 currentWidth = i;
18 }
19 }
20 result[0] = totalLines;
21 result[1] = prefixSum[strlen(s)] - prefixSum[currentWidth];
22}
23
24int main() {
25 int widths[26] = {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};
26 char s[] = "bbbcccdddaaa";
27 int result[2];
28 numberOfLines(widths, 26, s, result);
29 printf("[%d, %d]\n", result[0], result[1]);
30 return 0;
31}
32In this solution, we first compute a prefix sum array where prefixSum[i] contains the total width of the first i characters. We then iterate through the prefix sum to determine where the line widths exceed 100, marking new line starts and updating currentWidth.