Number of Lines To Write String

We’ll solve this problem by writing out the given string s on multiple lines, taking care to not exceed 100 pixels on any line. Here’s how we can do it:

Approach

  • Initialize Variables: We need two variables: lines to keep track of the total number of lines, and current_width to keep track of the width of the current line. Initialize lines to 1 and current_width to 0.
  • Loop through the Characters: Iterate through each character c in the given string s.
    • Find Width: Determine the width of c using the widths array. The index in the widths array is determined by the ASCII code of c minus the ASCII code of 'a'.
    • Check Width: If adding the width of c to current_width exceeds 100, increment lines by 1, and set current_width to the width of c.
    • Add Width: If it does not exceed 100, just add the width of c to current_width.
  • Return Result: Return [lines, current_width] as the final result.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

class Solution:
    def numberOfLines(self, widths: List[int], s: str) -> List[int]:
        lines = 1
        current_width = 0
        
        for c in s:
            width_of_c = widths[ord(c) - ord('a')]
            if current_width + width_of_c > 100:
                lines += 1
                current_width = width_of_c
            else:
                current_width += width_of_c
                
        return [lines, current_width]

Explanation

  • ord(c) - ord('a') helps us find the index of c in the widths array.
  • The loop iterates through each character, checks if it can be added to the current line without exceeding 100 pixels, and updates the variables accordingly.
  • The final result gives the total number of lines and the width of the last line.

This solution efficiently calculates the required output by going through the given string once, and it adheres to the constraints and requirements of the problem.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

def numberOfLines(widths, S):
    lines = 1
    res = []
    occupied_width = 0
    len_S = len(S)

    for i in range(len_S):
        if (occupied_width + widths[ord(S[i]) - ord('a')]) > 100:
            lines += 1
            occupied_width = 0
        occupied_width += widths[ord(S[i]) - ord('a')]

    res.append(lines)
    res.append(occupied_width)

    return res

Problem Classification

The problem is related to string manipulation and array traversal.

‘What’ Components:

  1. We are given a string of lowercase English letters, s.
  2. We are also given an array, widths, of size 26 where each element denotes the pixel width of corresponding English lowercase letters.
  3. We need to write the string s over several lines where each line is a maximum of 100 pixels wide.
  4. We are asked to return an array, result:
    • result[0]: the total number of lines required to write the string s.
    • result[1]: the width of the last line in pixels.

This problem can be classified as an ‘Iteration / Traversal’ and ‘Simulation’ problem.

  1. ‘Iteration / Traversal’: We need to iterate over each character of the string s and calculate its width using the given widths array. We also keep track of the total width and the number of lines used.
  2. ‘Simulation’: We are simulating the process of writing the string s over multiple lines following a set of rules (i.e., each line should not exceed 100 pixels).

To solve the problem, we need to combine the concepts of string manipulation, array traversal, and condition-based decision making.

Language Agnostic Coding Drills

  1. Dissection of Code:

The code can be dissected into the following distinct concepts:

a. Data types: Understanding the basic data types like integer, list, and string.

b. Array/ List manipulation: This includes accessing elements from a list and using the ‘append’ method to add elements into a list.

c. String manipulation: This includes iterating over a string and converting characters to ASCII using the ‘ord’ function.

d. Loops: Using ‘for’ loop to iterate over elements of a string.

e. Conditional statements: Using ‘if’ statement to perform conditional operations.

  1. Order of Coding Concepts (increasing difficulty):

    a. Data types (Easy): These are the building blocks of any programming language.

    b. Array/List manipulation (Easy): Essential for handling and operating on data.

    c. String manipulation (Medium): Involves operations on string characters and understanding ASCII values for character manipulation.

    d. Loops (Medium): Essential for repetitive operations, needs understanding of loop variables and loop conditions.

    e. Conditional statements (Medium): Essential for decision making in code. Requires understanding of condition checks and logical operators.

  2. Problem-solving Approach:

    a. Initialization: Initialize the required variables - ’lines’ to keep track of the number of lines, ‘occupied_width’ to keep track of the width used, and ‘res’ to store the result.

    b. Iteration: Iterate over each character in the string. Calculate the width of the current character by mapping it to the ‘widths’ array.

    c. Condition Check: If adding the width of the current character to ‘occupied_width’ exceeds 100, increment ’lines’ by 1 and reset ‘occupied_width’ to 0. After the check, add the width of the current character to ‘occupied_width’.

    d. Result Preparation: After the loop, append ’lines’ and ‘occupied_width’ to ‘res’.

    e. Return the Result: Finally, return the ‘res’ array. This represents the number of lines and the width of the last line. Each of the identified coding concepts contributes to different parts of the solution and combining them all in the right order gives us the final solution.

Targeted Drills in Python

  1. Python Coding Drills:

a. Data Types:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

# integers
num = 5
print(type(num))

# strings
text = 'Hello'
print(type(text))

# list
my_list = [1, 2, 3, 4, 5]
print(type(my_list))

b. List Manipulation:

1
2
3
4
5
6
7
8

my_list = [1, 2, 3, 4, 5]

# accessing elements from a list
print(my_list[2])

# append method to add elements into a list
my_list.append(6)
print(my_list)

c. String Manipulation:

1
2
3
4
5
6
7
8
9

my_string = "Hello"

# iterating over a string
for char in my_string:
    print(char)

# converting characters to ASCII
ascii_val = ord('a')
print(ascii_val)

d. Loops:

1
2
3

# using 'for' loop to iterate over elements
for i in range(5):
    print(i)

e. Conditional Statements:

1
2
3
4
5
6

# using 'if' statement to perform conditional operations
num = 5
if num > 3:
    print("Number is greater than 3")
else:
    print("Number is not greater than 3")
  1. Problem-Specific Drills:

Our problem doesn’t have any specific coding drills other than the general concepts. Understanding and implementing the general concepts are enough to solve this problem.

  1. Integration of Coding Drills:

To solve the problem, these pieces would be integrated in the following way:

a. Data types and list manipulations: Initialize the required variables - ’lines’, ‘occupied_width’, and ‘res’. Use a list ‘widths’ to store the width of each character and a string ‘S’ to store the input string.

b. Loops and string manipulations: Iterate over each character in the string ‘S’. Convert each character to its ASCII representation to calculate the width of the current character.

c. Conditional statements: Check if adding the width of the current character to ‘occupied_width’ exceeds 100. If it does, increment ’lines’ by 1 and reset ‘occupied_width’ to 0. After the check, add the width of the current character to ‘occupied_width’.

d. List manipulation: After the loop, append ’lines’ and ‘occupied_width’ to ‘res’.

e. Data types: Finally, return ‘res’. The final result would be a list containing the total number of lines and the width of the last line.