Problem

Given a string s and an integer k, break up the string into multiple lines such that each line has a length of k or less. You must break it up so that words don’t break across lines. Each line has to have the maximum possible amount of words. If there’s no way to break the text up, then return null.

You can assume that there are no spaces at the ends of the string and that there is exactly one space between each word.

Examples

Example 1

Input: s = "the quick brown fox jumps over the lazy dog", k = 10
Output: ["the quick", "brown fox", "jumps over", "the lazy", "dog"]
Explanation: Each line has a length of 10 or less with maximum words per line and no words are split across lines.

Example 2

Input: s = "hello world", k = 5
Output: null
Explanation: The word "hello" or "world" cannot fit within the limit of 5 characters.

Solution

Method 1 - Iteration

  • Start by splitting the string into individual words.
  • Initialize an empty list to store the lines and an empty string to accumulate words for the current line.
  • Iterate through each word, and for each word, check if adding it to the current line will exceed the length k.
  • If it exceeds, add the current line to the list of lines and start a new line with the current word.
  • Continue this process until all words have been processed.
  • Add the last line to the list of lines after processing all words.

Approach

  1. Split the String: Split the string s by spaces to get individual words.
  2. Initializations: Initialize a list to store lines and a string to build the current line.
  3. Iterate Through Words: For each word, check if it can be added to the current line without exceeding k:
    • If yes, add it to the current line.
    • If no, add the current line to the list of lines and start a new line with the current word.
  4. Edge Case: If any word exceeds k, immediately return null.
  5. Final Append: After the loop, add the last line to the list of lines.

Code

Java
public class Solution {
    public List<String> breakString(String s, int k) {
        String[] words = s.split(" ");
        List<String> result = new ArrayList<>();
        StringBuilder currentLine = new StringBuilder();

        for (String word : words) {
            if (word.length() > k) {
                return null; // If any word is longer than k, return null
            }
            if (currentLine.length() + word.length() + (currentLine.length() > 0 ? 1 : 0) > k) {
                result.add(currentLine.toString());
                currentLine = new StringBuilder();
            }
            if (currentLine.length() > 0) {
                currentLine.append(" ");
            }
            currentLine.append(word);
        }
        if (currentLine.length() > 0) {
            result.add(currentLine.toString());
        }

        return result;
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        System.out.println(solution.breakString("the quick brown fox jumps over the lazy dog", 10));
        // Output: ["the quick", "brown fox", "jumps over", "the lazy", "dog"]

        System.out.println(solution.breakString("hello world", 5)); // Output: null
    }
}
Python
class Solution:
    def breakString(self, s: str, k: int) -> Optional[List[str]]:
        words = s.split(" ")
        result = []
        current_line = ""

        for word in words:
            if len(word) > k:
                return None  # If any word is longer than k, return None
            if len(current_line) + len(word) + (1 if current_line else 0) > k:
                result.append(current_line)
                current_line = ""
            if current_line:
                current_line += " "
            current_line += word
        
        if current_line:
            result.append(current_line)
        
        return result

# For testing the solution
if __name__ == "__main__":
    solution = Solution()
    print(solution.breakString("the quick brown fox jumps over the lazy dog", 10))
    # Output: ["the quick", "brown fox", "jumps over", "the lazy", "dog"]

    print(solution.breakString("hello world", 5))  # Output: None

Complexity

  • ⏰ Time complexity: O(n) where n is the length of the string s.
  • 🧺 Space complexity:  O(n) for the resulting list of lines.