Count Substrings with Only One Distinct Letter

🏠 ⬅️ ➡️

Given a string s, return the number of substrings that have only one distinct letter.

Example 1:

Input: s = "aaaba " Output: 8 Explanation: The substrings with one distinct letter are "aaa ", "aa ", "a ", "b ". "aaa " occurs 1 time. "aa " occurs 2 times. "a " occurs 4 times. "b " occurs 1 time. So the answer is 1 + 2 + 4 + 1 = 8.

Example 2:

Input: s = "aaaaaaaaaa " Output: 55

Constraints:

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

    character(len=:), allocatable :: s
    integer :: n_substrings, i

    ! Example 1
    s = "aaaba"
    print '(A)', solve(s)

    ! Example 2
    s = "aaaaaaaaaa"
    print '(A)', solve(s)

contains

    function solve(s) result(n_substrings)
        implicit none
        character(len=*), intent(in) :: s
        integer :: n_substrings, i, j
        logical :: first_letter

        n_substrings = 0
        do i = 1, len(s)-1
            first_letter = .true.
            do j = i+1, len(s)
                if (first_letter .and. s(j:j) == s(i:i)) then
                    first_letter = .false.
                else if (.not. first_letter .and. s(j:j) /= s(i:i)) then
                    exit
                end if
            end do
            if (first_letter) then
                n_substrings = n_substrings + 1
            end if
        end do
    end function solve

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

      integer :: i, j, count
      character(len=1000) :: s

      ! read input
      read (*, *) s

      ! initialize count
      count = 0

      ! loop through each substring
      do i = 1, len(s) - 1
          ! loop through each letter in the substring
          do j = i, len(s)
              ! if the letter is not the same as the previous letter, increment count
              if (s(j:j) /= s(j-1:j-1)) then
                  count = count + 1
              end if
          end do
      end do

      ! print output
      write (*, *) count

      end program count_unique_substrings
🌐 Data from online sources 
def count_letters(s: str) -> int:
    count = 0
    current = 1

    for i in range(1, len(s)):
        if s[i] == s[i - 1]:
            current += 1
        else:
            count += (current * (current + 1)) // 2
            current = 1

    count += (current * (current + 1)) // 2
    return count

The algorithm iterates through the string s and checks if the current character is same as the previous character. If yes, it increments the current counter. When it finds a different character, it calculates the count of distinct single-letter substrings ending prior to that character and adds the count to the count variable. The formula (current * (current + 1)) / 2 is the sum of the first current positive integers, which is the number of substrings that can be formed with the same character. This process is repeated for each character in the string. Finally, the total count of substrings is returned.

🌐 Data from online sources 
int countLetters(string s) {
    int count = 0, current = 1;

    for (int i = 1; i < s.length(); i++) {
        if (s[i] == s[i - 1]) {
            current++;
        } else {
            count += (current * (current + 1)) / 2;
            current = 1;
        }
    }

    count += (current * (current + 1)) / 2;
    return count;
}

The algorithm iterates through the string s and checks if the current character is same as the previous character. If yes, it increments the current counter. When it finds a different character, it calculates the count of distinct single-letter substrings ending prior to that character and adds the count to the count variable. The formula (current * (current + 1)) / 2 is the sum of the first current positive integers, which is the number of substrings that can be formed with the same character. This process is repeated for each character in the string. Finally, the total count of substrings is returned.