Check Distances Between Same Letters

🏠 ⬅️ ➡️

You are given a 0-indexed string s consisting of only lowercase English letters, where each letter in s appears exactly twice. You are also given a 0-indexed integer array distance of length 26.

Each letter in the alphabet is numbered from 0 to 25 (i.e. 'a' -> 0, 'b' -> 1, 'c' -> 2, ... , 'z' -> 25).

In a well-spaced string, the number of letters between the two occurrences of the ith letter is distance[i]. If the ith letter does not appear in s, then distance[i] can be ignored.

Return true if s is a well-spaced string, otherwise return false.

Example 1:

Input: s = "abaccb ", distance = [1,3,0,5,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0] Output: true Explanation: - 'a' appears at indices 0 and 2 so it satisfies distance[0] = 1. - 'b' appears at indices 1 and 5 so it satisfies distance[1] = 3. - 'c' appears at indices 3 and 4 so it satisfies distance[2] = 0. Note that distance[3] = 5, but since 'd' does not appear in s, it can be ignored. Return true because s is a well-spaced string.

Example 2:

Input: s = "aa ", distance = [1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0] Output: false Explanation: - 'a' appears at indices 0 and 1 so there are zero letters between them. Because distance[0] = 1, s is not a well-spaced string.

Constraints:

  • 2 <= s.length <= 52
  • s consists only of lowercase English letters.
  • Each letter appears in s exactly twice.
  • distance.length == 26
  • 0 <= distance[i] <= 50
Note: This problem is from LeetCode.
❌ Compiled
❌ Executed
❌ Correct 
program main
    implicit none

    character(len=52) :: s
    integer, dimension(26) :: distance
    logical :: result

    ! Examples taken from the problem statement
    s = "abaccb "
    distance = [1,3,0,5,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0]
    result = wellSpacedString(s, distance)
    write (*,*) result

    s = "aa "
    distance = [1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0]
    result = wellSpacedString(s, distance)
    write (*,*) result

contains

logical function wellSpacedString(s, distance)
    implicit none
    character(len=*), intent(in) :: s
    integer, dimension(:), intent(in) :: distance
    integer :: i, j, k

    wellSpacedString = .true.

    do i = 0, 25
        if (s(i+1:i+1) /= '') then
            j = index(s, s(i+1:i+1))
            k = index(s, s(i+1:i+1), back=.true.)
            if (j > k) then
                wellSpacedString = .false.
                exit
            end if
            if (k - j < distance(i)) then
                wellSpacedString = .false.
                exit
            end if
        end if
    end do
end function wellSpacedString

end program main
❌ Compiled
❌ Executed
❌ Correct 
module well_spaced_string

implicit none

contains

function is_well_spaced_string(s, distance) result(is_well_spaced)

! Given a string s consisting of only lowercase English letters, where each letter appears exactly twice.
! Given a 0-indexed integer array distance of length 26.
! Each letter in the alphabet is numbered from 0 to 25 (i.e. 'a' -> 0, 'b' -> 1, 'c' -> 2, ..., 'z' -> 25).
! In a well-spaced string, the number of letters between the two occurrences of the ith letter is distance[i].
! If the ith letter does not appear in s, then distance[i] can be ignored.
! Return true if s is a well-spaced string, otherwise return false.

character(len=*), intent(in) :: s
integer, intent(in) :: distance(:)
logical :: is_well_spaced

! Edge case: If the string is empty, return true
if (len(trim(s)) == 0) then
    is_well_spaced = .true.
    return
end if

! Initialize the indices of the first and second occurrences of each letter
integer :: first_index(26), second_index(26)
first_index = -1
second_index = -1

! Loop through the string and keep track of the indices of the first and second occurrences of each letter
do i = 1, len(s)
    if (first_index(iachar(s(i:i))) == -1) then
        first_index(iachar(s(i:i))) = i
    else
        second_index(iachar(s(i:i))) = i
    end if
end do

! Check if the distance between the two occurrences of each letter is valid
do i = 1, 26
    if (first_index(i) == -1 .or. second_index(i) == -1) then
        ! If a letter does not appear in the string, the distance can be ignored
        cycle
    else if (second_index(i) - first_index(i) == distance(i)) then
        ! If the distance between the two occurrences of the letter is valid, continue
        cycle
    else
        ! If the distance between the two occurrences of the letter is not valid, return false
        is_well_spaced = .false.
        return
    end if
end do

! If we reach this point, the string is a well-spaced string
is_well_spaced = .true.

end function is_well_spaced_string

end module well_spaced_string

! Test the function with the given examples
program test_well_spaced_string

use well_spaced_string

implicit none

! Examples from the problem statement
character(len=10) :: s
integer :: distance(26)
logical :: is_well_spaced

! Example 1
s = "abaccb "
distance = [1,3,0,5,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0]
is_well_spaced = is_well_spaced_string(s, distance)
write (*,*) "Example 1: ", is_well_spaced

! Example 2
s = "aa "
distance = [1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0]
is_well_spaced = is_well_spaced_string(s, distance)
write (*,*) "Example 2: ", is_well_spaced

end program test_well_spaced_string
🌐 Data from online sources 
def well_spaced_string(s: str, distance: List[int]) -> bool:
    first = {}
    for i, c in enumerate(s):
        if c not in first:
            first[c] = i
        else:
            if distance[ord(c) - ord('a')] != i - first[c] - 1:
                return False
    return True

The algorithm iterates through the characters of the given string s. If it encounters a character for the first time, it stores the character along with its index in a map first. If it encounters the character for the second time, it checks whether the difference between the current index and the first occurrence of the character minus 1 is equal to the required distance given in the distance array. If this condition is not met, the function returns false. If the iteration is completed without failing the condition, the function returns true.

🌐 Data from online sources 
bool wellSpacedString(std::string s, std::vector<int> distance) {
    std::unordered_map<char, int> first;
    for (int i = 0; i < s.size(); ++i) {
        char c = s[i];
        if (first.find(c) == first.end()) {
            first[c] = i;
        } else {
            if (distance[c - 'a'] != i - first[c] - 1) {
                return false;
            }
        }
    }
    return true;
}

The algorithm iterates through the characters of the given string s. If it encounters a character for the first time, it stores the character along with its index in a map first. If it encounters the character for the second time, it checks whether the difference between the current index and the first occurrence of the character minus 1 is equal to the required distance given in the distance array. If this condition is not met, the function returns false. If the iteration is completed without failing the condition, the function returns true.