Count the Number of Consistent Strings

🏠 ⬅️ ➡️

You are given a string allowed consisting of distinct characters and an array of strings words. A string is consistent if all characters in the string appear in the string allowed.

Return the number of consistent strings in the array words.

Example 1:

Input: allowed = "ab ", words = [ "ad ", "bd ", "aaab ", "baa ", "badab "] Output: 2 Explanation: Strings "aaab " and "baa " are consistent since they only contain characters 'a' and 'b'.

Example 2:

Input: allowed = "abc ", words = [ "a ", "b ", "c ", "ab ", "ac ", "bc ", "abc "] Output: 7 Explanation: All strings are consistent.

Example 3:

Input: allowed = "cad ", words = [ "cc ", "acd ", "b ", "ba ", "bac ", "bad ", "ac ", "d "] Output: 4 Explanation: Strings "cc ", "acd ", "ac ", and "d " are consistent.

Constraints:

  • 1 <= words.length <= 104
  • 1 <= allowed.length <= 26
  • 1 <= words[i].length <= 10
  • The characters in allowed are distinct.
  • words[i] and allowed contain only lowercase English letters.
Note: This problem is from LeetCode.
❌ Compiled
❌ Executed
❌ Correct 
program main
    implicit none

    character(len=*), parameter :: allowed = "ab "
    character(len=*), parameter :: words(5) = ["ad ", "bd ", "aaab ", "baa ", "badab "]
    integer :: n_consistent

    n_consistent = count_consistent(allowed, words)
    write (*, "(A, I0)") "Number of consistent strings:", n_consistent

contains

    function count_consistent(allowed, words) result(n)
        implicit none
        character(len=*), intent(in) :: allowed
        character(len=*), intent(in) :: words(:)
        integer :: i, j, n

        do i = 1, size(words)
            do j = 1, len(words(i))
                if (index(allowed, words(i)(j:j)) == 0) then
                    exit
                end if
            end do
            if (j > len(words(i))) then
                n = n + 1
            end if
        end do
    end function count_consistent
end program main
✅ Compiled
❌ Executed
❌ Correct 
program consistent_strings
      implicit none

      integer :: i, j, n, m, count
      character(len=10) :: allowed
      character(len=10), dimension(:), allocatable :: words

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

      ! Initialize count
      count = 0

      ! Check each word
      do i = 1, n
         ! Check if word is consistent
         if (check_consistency(words(i), allowed)) then
            count = count + 1
         end if
      end do

      ! Print output
      write(*,*) count

      contains

         ! Check if a string is consistent
         pure function check_consistency(word, allowed) result(consistent)
         implicit none
         character(len=*), intent(in) :: word
         character(len=*), intent(in) :: allowed
         logical :: consistent
         integer :: i

         ! Initialize consistent
         consistent = .true.

         ! Check if all characters in word are in allowed
         do i = 1, len(word)
            if (index(allowed, word(i:i)) == 0) then
               consistent = .false.
               exit
            end if
         end do

         end function check_consistency

      end program consistent_strings
🌐 Data from online sources 
def find_latest_step(arr, m):
    n = len(arr)
    length_left, length_right = [0] * (n + 2), [0] * (n + 2)
    count, result = 0, -1

    for i, pos in enumerate(arr):
        left_length = length_right[pos - 1]
        right_length = length_left[pos + 1]
        new_length = left_length + right_length + 1

        if left_length == m or right_length == m:
            count -= 1

        if new_length == m:
            count += 1

        if new_length > 0:
            length_left[pos - left_length] = new_length
            length_right[pos + right_length] = new_length
            result = i + 1

    return result if count > 0 else -1

The algorithm initializes two arrays `lengthLeft` and `lengthRight` to keep track of the left and right lengths of contiguous groups of 1's. It also initializes a `count` variable that will be incremented when finding a group of 1's with length `m` and decremented when a group of 1's is extended beyond length `m`.

For each step i from 1 to n, the position in the binary string is set to 1 using the value from the array arr. The left length, right length, and total new length of the newly created group of 1's is then calculated using lengthLeft and lengthRight.

After calculating the new lengths, we modify the count: - If the left length is equal to m or the right length is equal to m, decrement the count - If the new length is equal to m, increment the count

After that, if the new length is greater than 0, we set the values of new left and right lengths in lengthLeft and lengthRight arrays and update the result with the current step i + 1.

Once all steps are completed, if the count is greater than 0, then the result is returned. If the count is 0 or less, then we return -1 as no such group of 1's exists with length m.

🌐 Data from online sources 
int findLatestStep(vector<int>& arr, int m) {
    int n = arr.size();
    vector<int> lengthLeft(n + 2, 0), lengthRight(n + 2, 0);
    int count = 0, result = -1;

    for (int i = 0; i < n; ++i) {
        int pos = arr[i];
        int leftLength = lengthRight[pos - 1];
        int rightLength = lengthLeft[pos + 1];
        int newLength = leftLength + rightLength + 1;

        if (leftLength == m || rightLength == m) {
            count--;
        }

        if (newLength == m) {
            count++;
        }

        if (newLength > 0) {
            lengthLeft[pos - leftLength] = newLength;
            lengthRight[pos + rightLength] = newLength;
            result = i + 1;
        }
    }

    return count > 0 ? result : -1;
}

The algorithm initializes two arrays `lengthLeft` and `lengthRight` to keep track of the left and right lengths of contiguous groups of 1's. It also initializes a `count` variable that will be incremented when finding a group of 1's with length `m` and decremented when a group of 1's is extended beyond length `m`.

For each step i from 1 to n, the position in the binary string is set to 1 using the value from the array arr. The left length, right length, and total new length of the newly created group of 1's is then calculated using lengthLeft and lengthRight.

After calculating the new lengths, we modify the count: - If the left length is equal to m or the right length is equal to m, decrement the count - If the new length is equal to m, increment the count

After that, if the new length is greater than 0, we set the values of new left and right lengths in lengthLeft and lengthRight arrays and update the result with the current step i + 1.

Once all steps are completed, if the count is greater than 0, then the result is returned. If the count is 0 or less, then we return -1 as no such group of 1's exists with length m.