Check if All Characters Have Equal Number of Occurrences

🏠 ⬅️ ➡️

Given a string s, return true if s is a good string, or false otherwise.

A string s is good if all the characters that appear in s have the same number of occurrences (i.e., the same frequency).

Example 1:

Input: s = "abacbc " Output: true Explanation: The characters that appear in s are 'a', 'b', and 'c'. All characters occur 2 times in s.

Example 2:

Input: s = "aaabb " Output: false Explanation: The characters that appear in s are 'a' and 'b'. 'a' occurs 3 times while 'b' occurs 2 times, which is not the same number of times.

Constraints:

  • 1 <= s.length <= 1000
  • s consists of lowercase English letters.
Note: This problem is from LeetCode.
❌ Compiled
❌ Executed
❌ Correct 
program main
    implicit none

    character(len=:), allocatable :: s
    logical :: good

    ! Example 1
    s = "abacbc "
    good = goodString(s)
    print *, good

    ! Example 2
    s = "aaabb "
    good = goodString(s)
    print *, good

contains

    function goodString(s) result(good)
        implicit none
        character(len=*), intent(in) :: s
        integer :: count(26)
        integer :: i

        do i = 1, size(count)
            count(i) = 0
        end do

        do i = 1, len(s)
            count(ichar(s(i:i)) - ichar('a') + 1) = count(ichar(s(i:i)) - ichar('a') + 1) + 1
        end do

        good = .true.
        do i = 1, size(count)
            if (count(i) /= count(1)) then
                good = .false.
                exit
            end if
        end do

    end function goodString

end program main
✅ Compiled
❌ Executed
❌ Correct 
module good_string

implicit none

contains

function is_good_string(s) result(is_good)

character(len=*), intent(in) :: s
logical :: is_good

! Local variables
integer :: char_count(26)
integer :: i

! Initialize the character count array
char_count = 0

! Count the number of occurrences of each character in s
do i = 1, len(s)
    char_count(ichar(s(i:i))) = char_count(ichar(s(i:i))) + 1
end do

! Check if all characters have the same number of occurrences
is_good = .true.
do i = 1, 26
    if (char_count(i) > 0) then
        if (any(char_count(i+1:26) /= char_count(i))) then
            is_good = .false.
            exit
        end if
    end if
end do

end function is_good_string

end module good_string

program test_good_string

use good_string

implicit none

! Test case 1:
print *, is_good_string("abacbc ")
! Expected output:
! true

! Test case 2:
print *, is_good_string("aaabb ")
! Expected output:
! false

! Test case 3:
print *, is_good_string("abcdefghijklmnopqrstuvwxyz ")
! Expected output:
! true

! Test case 4:
print *, is_good_string("abcd")
! Expected output:
! false

! Test case 5:
print *, is_good_string("")
! Expected output:
! true

end program test_good_string
🌐 Data from online sources 
def make_string_sorted(s):
    mod = 1000000007
    n = len(s)
    fact = [1] * (n + 1)
    inv = [1] * (n + 1)
    for i in range(1, n + 1):
        fact[i] = fact[i - 1] * i % mod
        inv[i] = inv[i - 1] * (mod - mod // i) % mod

    ans = 0
    for i in range(n):
        less_than = 0
        for j in range(i + 1, n):
            if s[j] < s[i]:
                less_than += 1
        ans = (ans + less_than * fact[n - i - 1]) % mod
    return ans

The algorithm consists of the following steps:

  1. Initialize the factorials and inverse factorials for numbers up to the length of the given string, using modulo arithmetic.
  2. For each character in the string, count the number of characters to the right that are less than the current character.
  3. Multiply that count by the factorial of the number of remaining characters to the right, modulo the large prime number, and add it to the result.

In this way, the algorithm takes into account all possible permutations generated through the process of sorting, accumulating the required operations to make the string sorted.

🌐 Data from online sources 
int makeStringSorted(string s) {
    const int mod = 1e9 + 7;
    int n = s.size();
    vector<int> fact(n + 1, 1);
    vector<int> inv(n + 1, 1);
    for (int i = 1; i <= n; ++i) {
        fact[i] = 1LL * fact[i - 1] * i % mod;
        inv[i] = 1LL * inv[i - 1] * (mod - mod / i) % mod;
    }
    int ans = 0;
    for (int i = 0; i < n; ++i) {
        int less_than = 0;
        for (int j = i + 1; j < n; ++j) {
            if (s[j] < s[i]) ++less_than;
        }
        ans = (ans + 1LL * less_than * fact[n - i - 1] % mod) % mod;
    }
    return ans;
}

The algorithm consists of the following steps:

  1. Initialize the factorials and inverse factorials for numbers up to the length of the given string, using modulo arithmetic.
  2. For each character in the string, count the number of characters to the right that are less than the current character.
  3. Multiply that count by the factorial of the number of remaining characters to the right, modulo the large prime number, and add it to the result.

In this way, the algorithm takes into account all possible permutations generated through the process of sorting, accumulating the required operations to make the string sorted.