Problem

Given a rows x cols screen and a sentence represented by a list of non-empty words, find how many times the given sentence can be fitted on the screen.

Note:

  1. A word cannot be split into two lines.
  2. The order of words in the sentence must remain unchanged.
  3. Two consecutive words in a line must be separated by a single space.
  4. Total words in the sentence won’t exceed 100.
  5. Length of each word is greater than 0 and won’t exceed 10.
  6. 1 ≤ rows, cols ≤ 20,000.

Examples

Example 1:

Input: rows = 2, cols = 8, sentence = ["hello", "world"]
Output: 1
Explanation:
hello---
world---

The character '-' signifies an empty space on the screen.

Example 2:

Input: rows = 3, cols = 6, sentence = ["a", "bcd", "e"]
Output:  2
Explanation:
a-bcd- 
e-a---
bcd-e-

The character '-' signifies an empty space on the screen.

Example 3:

Input: rows = 4, cols = 5, sentence = ["I", "had", "apple", "pie"]
Output:  1
Explanation:
I-had
apple
pie-I
had--

The character '-' signifies an empty space on the screen.

Solution

Method 1 - Greedy

At first, I found it very complicated to figure out how to place individual words into the matrix. However, after seeing kylejao’s solution, I realized you can preprocess the strings by concatenating them into a single long string with spaces between each word.

For example, [“abc”, “de”, “f”] becomes “abc de f ”.

The length represents the total length of the concatenated string including spaces.

The count indicates how many valid characters have been placed.

The goal is to determine count/length, representing how many times the string fits.

A greedy approach works best: try to fit as many words in one line as possible and manage the leftover words that don’t fit by moving them to the next line. For instance, place “abc de ” (6 columns, 6 characters) in the first row and examine the 7th character.

If it’s a space, it means the first row fits perfectly. Continue to the next row with the 8th character.

If it’s not a space, you are in the middle of a word. Move one character back at a time (reducing count) until you find a space to ensure words don’t split.

Illustration:

0      7     13          25
abc de f abc de f abc de f
XXXXXX
	XXXXXX 
		  XXXXXX
			   XXXXXX 
					  X....
abc-de
f-abc-
de-f--
abc-de
f...

To fit the given sentence on a screen of rows and cols, we can follow a greedy approach that simulates the placement of characters:

  1. Concatenate Sentence to a String with Spaces: Create a single string from the sentence words appended with spaces (e.g., ["abc", "de", "f"] becomes "abc de f "). This helps in handling boundary cases, allowing for easy word wrap detection.
  2. Use Index to Track Placement: Maintain a variable cur to keep track of the current index within the created string.
  3. Simulate Row Addition:
    • Increment the current position by the number of columns (cur += cols).
    • Check the position after the word addition:
      • If it lands on a space (s[cur % len(s)] == ' '), it means we perfectly placed the word, so increment the index by one to move to the next character.
      • If it doesn’t land on a space, move backward to find the last space to ensure words are not split.
  4. Count Full Fits: By the end of all rows, the index divided by the length of the concatenated string (cur / len(s)) gives the number of times the sentence can fit.

Code

C++
class Solution {
public:
    int wordsTyping(vector<string>& sentence, int rows, int cols) {
        string s;
        for (auto& t : sentence) {
            s += t;
            s += " ";
        }
        int m = s.size();
        int cur = 0;
        while (rows--) {
            cur += cols;
            if (s[cur % m] == ' ') {
                ++cur;
            } else {
                while (cur && s[(cur - 1) % m] != ' ') {
                    --cur;
                }
            }
        }
        return cur / m;
    }
};
Go
func wordsTyping(sentence []string, rows int, cols int) int {
	s := strings.Join(sentence, " ") + " "
	m := len(s)
	cur := 0
	for i := 0; i < rows; i++ {
		cur += cols
		if s[cur%m] == ' ' {
			cur++
		} else {
			for cur > 0 && s[(cur-1)%m] != ' ' {
				cur--
			}
		}
	}
	return cur / m
}
Java
class Solution {
    public int wordsTyping(String[] sentence, int rows, int cols) {
        String s = String.join(" ", sentence) + " ";
        int m = s.length();
        int cur = 0;
        while (rows-- > 0) {
            cur += cols;
            if (s.charAt(cur % m) == ' ') {
                ++cur;
            } else {
                while (cur > 0 && s.charAt((cur - 1) % m) != ' ') {
                    --cur;
                }
            }
        }
        return cur / m;
    }
}
Python
class Solution:
    def wordsTyping(self, sentence: List[str], rows: int, cols: int) -> int:
        s = " ".join(sentence) + " "
        m = len(s)
        cur = 0
        for _ in range(rows):
            cur += cols
            if s[cur % m] == " ":
                cur += 1
            while cur and s[(cur - 1) % m] != " ":
                cur -= 1
        return cur // m
Typescript
function wordsTyping(sentence: string[], rows: number, cols: number): number {
    const s = sentence.join(' ') + ' ';
    let cur = 0;
    const m = s.length;
    for (let i = 0; i < rows; ++i) {
        cur += cols;
        if (s[cur % m] === ' ') {
            ++cur;
        } else {
            while (cur > 0 && s[(cur - 1) % m] !== ' ') {
                --cur;
            }
        }
    }
    return Math.floor(cur / m);
}

…