Maximum Number of Words Found in Sentences

🏠 ⬅️ ➡️

A sentence is a list of words that are separated by a single space with no leading or trailing spaces.

You are given an array of strings sentences, where each sentences[i] represents a single sentence.

Return the maximum number of words that appear in a single sentence.

Example 1:

Input: sentences = [ "alice and bob love leetcode ", "i think so too ", "this is great thanks very much "] Output: 6 Explanation: - The first sentence, "alice and bob love leetcode ", has 5 words in total. - The second sentence, "i think so too ", has 4 words in total. - The third sentence, "this is great thanks very much ", has 6 words in total. Thus, the maximum number of words in a single sentence comes from the third sentence, which has 6 words.

Example 2:

Input: sentences = [ "please wait ", "continue to fight ", "continue to win "] Output: 3 Explanation: It is possible that multiple sentences contain the same number of words. In this example, the second and third sentences (underlined) have the same number of words.

Constraints:

  • 1 <= sentences.length <= 100
  • 1 <= sentences[i].length <= 100
  • sentences[i] consists only of lowercase English letters and ' ' only.
  • sentences[i] does not have leading or trailing spaces.
  • All the words in sentences[i] are separated by a single space.
Note: This problem is from LeetCode.
❌ Compiled
❌ Executed
❌ Correct 
program main
    implicit none

    integer :: i, j, n, m
    character(len=100), allocatable :: sentences(:)
    integer, allocatable :: counts(:)

    call get_examples()

contains

    subroutine get_examples()
        implicit none

        integer, parameter :: num_examples = 2
        character(len=100), parameter :: examples(num_examples, *) = reshape([character(len=100) :: &
            ["alice and bob love leetcode ", "i think so too ", "this is great thanks very much "], &
            ["please wait ", "continue to fight ", "continue to win "]], shape(examples))

        do i = 1, num_examples
            allocate(sentences(size(examples(i, :))))
            do j = 1, size(sentences)
                sentences(j) = examples(i, j)
            end do
            write(*, "(A)", advance="no") "Example #", i, ": "
            write(*, "(A)") solve(sentences)
        end do

    end subroutine get_examples

    function solve(sentences) result(max_words)
        implicit none
        character(len=*), intent(in) :: sentences(:)
        integer :: max_words

        integer :: i, n
        character(len=:), allocatable :: words(:)

        n = size(sentences)
        allocate(counts(n))

        do i = 1, n
            call split(sentences(i), words)
            counts(i) = size(words)
        end do

        max_words = maxval(counts)

    end function solve

    subroutine split(str, words)
        implicit none
        character(len=*), intent(in) :: str
        character(len=:), allocatable, intent(out) :: words(:)

        integer :: i, pos

        allocate(words(0))

        do while (str /= "")
            pos = index(str, " ")
            if (pos == 0) then
                words = [words, trim(str)]
                exit
            else
                words = [words, trim(str(:pos-1))]
                str = str(pos+1:)
            end if
        end do

    end subroutine split

end program main
❌ Compiled
❌ Executed
❌ Correct 
module MaxWords
  implicit none
contains
  function max_words(sentences) result(max_words)
    character(len=*), intent(in) :: sentences(:)
    integer :: max_words, words
    integer :: i, j

    max_words = 0
    do i = 1, size(sentences)
      words = 0
      do j = 1, len_trim(sentences(i))
        if (sentences(i)(j:j) == ' ') then
          words = words + 1
        end if
      end do
      if (words > max_words) then
        max_words = words
      end if
    end do
  end function max_words
end module MaxWords

program test_max_words
  use MaxWords
  implicit none
  character(len=*), parameter :: sentences(3) = ["alice and bob love leetcode ", "i think so too ", "this is great thanks very much "]
  integer :: max_words

  max_words = max_words(sentences)
  write (*,*) "Max words:", max_words

  max_words = max_words(["please wait ", "continue to fight ", "continue to win "])
  write (*,*) "Max words:", max_words
end program test_max_words
🌐 Data from online sources 
def min_sessions(tasks, session_time):
    sessions = []
    tasks.sort(reverse=True)

    for task in tasks:
        added = False
        for session_idx, session in enumerate(sessions):
            if session + task <= session_time:
                sessions[session_idx] += task
                added = True
                break

        if not added:
            sessions.append(task)

    return len(sessions)

The algorithm starts by sorting the tasks array in descending order. Then, for each task in tasks, it iterates over the sessions array and tries to insert the task into the first session that has sufficient remaining time. If no session can accommodate the task, a new session is created.

In the end, the size of the sessions array is the answer, which represents the minimum number of work sessions required to finish all tasks.

🌐 Data from online sources 
#include <vector>
#include <algorithm>

int minSessions(std::vector<int>& tasks, int sessionTime) {
    std::sort(tasks.begin(), tasks.end(), std::greater<int>());
    std::vector<int> sessions;

    for (int task : tasks) {
        bool added = false;
        for (int& session : sessions) {
            if (session + task <= sessionTime) {
                session += task;
                added = true;
                break;
            }
        }

        if (!added) {
            sessions.push_back(task);
        }
    }

    return sessions.size();
}

The algorithm starts by sorting the tasks array in descending order. Then, for each task in tasks, it iterates over the sessions array and tries to insert the task into the first session that has sufficient remaining time. If no session can accommodate the task, a new session is created.

In the end, the size of the sessions array is the answer, which represents the minimum number of work sessions required to finish all tasks.