Count Prefixes of a Given String

🏠 ⬅️ ➡️

You are given a string array words and a string s, where words[i] and s comprise only of lowercase English letters.

Return the number of strings in words that are a prefix of s.

A prefix of a string is a substring that occurs at the beginning of the string. A substring is a contiguous sequence of characters within a string.

Example 1:

Input: words = [ "a ", "b ", "c ", "ab ", "bc ", "abc "], s = "abc " Output: 3 Explanation: The strings in words which are a prefix of s = "abc " are: "a ", "ab ", and "abc ". Thus the number of strings in words which are a prefix of s is 3.

Example 2:

Input: words = [ "a ", "a "], s = "aa " Output: 2 Explanation: Both of the strings are a prefix of s. Note that the same string can occur multiple times in words, and it should be counted each time.

Constraints:

  • 1 <= words.length <= 1000
  • 1 <= words[i].length, s.length <= 10
  • words[i] and s consist of lowercase English letters only.
Note: This problem is from LeetCode.
✅ Compiled
❌ Executed
❌ Correct 
program main
    implicit none

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

    call get_command_argument(1, s)
    read (s, *) n
    allocate (words(n))
    do i = 1, n
        call get_command_argument(i+1, s)
        read (s, *) words(i)
    end do

    print '(I0)', count_prefixes(words, s)

contains

    function count_prefixes(words, s) result(count)
        implicit none
        character(len=*), intent(in) :: words(:), s
        integer :: count
        integer :: i

        count = 0
        do i = 1, size(words)
            if (index(s, words(i)) == 1) then
                count = count + 1
            end if
        end do
    end function count_prefixes

end program main
✅ Compiled
❌ Executed
❌ Correct 
program count_prefixes
      implicit none

      integer :: i, j, n, m
      character(len=1000) :: s
      character(len=1000) :: words(1000)

      ! Read input
      read(*,*) n
      do i = 1, n
         read(*,*) words(i)
      end do
      read(*,*) s

      ! Initialize output
      m = 0

      ! Loop through words
      do i = 1, n
         ! Check if word is a prefix of s
         if (s(1:len_trim(words(i))) == words(i)) then
            m = m + 1
         end if
      end do

      ! Output result
      write(*,*) m

      end program count_prefixes
🌐 Data from online sources 
def minSwaps(nums):
    ones = maxOnes = currOnes = left = 0

    for num in nums:
        ones += num

    for right in range(len(nums)):
        currOnes += nums[right]

        if right - left + 1 > ones:
            currOnes -= nums[left]
            left += 1

        maxOnes = max(maxOnes, currOnes)

    return ones - maxOnes
  1. Count the total number of 1's in the array and store this value in the ones variable.
  2. Initialize variables maxOnes, currOnes, and left to 0. These will be used to keep track of the maximum number of 1's in a range and our current window.
  3. Loop through the array using the right variable.
  4. Add the value in nums[right] to currOnes.
  5. Check if the window size (between right and left) is greater than the total number of 1's.
  6. If it is, remove the value at nums[left] from currOnes, then increment left to reduce our window size.
  7. Update the maxOnes variable to store the maximum value between itself and currOnes.
  8. After looping through the entire array, subtract maxOnes from the total ones. The result is the minimum number of swaps needed.
🌐 Data from online sources 
int minSwaps(vector<int>& nums) {
    int ones = 0, maxOnes = 0, currOnes = 0, left = 0;

    for (int num : nums) {
        ones += num;
    }

    for (int right = 0; right < nums.size(); ++right) {
        currOnes += nums[right];

        if (right - left + 1 > ones) {
            currOnes -= nums[left];
            ++left;
        }

        maxOnes = max(maxOnes, currOnes);
    }

    return ones - maxOnes;
}
  1. Count the total number of 1's in the array and store this value in the ones variable.
  2. Initialize variables maxOnes, currOnes, and left to 0. These will be used to keep track of the maximum number of 1's in a range and our current window.
  3. Loop through the array using the right variable.
  4. Add the value in nums[right] to currOnes.
  5. Check if the window size (between right and left) is greater than the total number of 1's.
  6. If it is, remove the value at nums[left] from currOnes, then increment left to reduce our window size.
  7. Update the maxOnes variable to store the maximum value between itself and currOnes.
  8. After looping through the entire array, subtract maxOnes from the total ones. The result is the minimum number of swaps needed.