Count Pairs Of Similar Strings

🏠 ⬅️ ➡️

You are given a 0-indexed string array words.

Two strings are similar if they consist of the same characters.

  • For example, "abca " and "cba " are similar since both consist of characters 'a', 'b', and 'c'.
  • However, "abacba " and "bcfd " are not similar since they do not consist of the same characters.

Return the number of pairs (i, j) such that 0 <= i < j <= word.length - 1 and the two strings words[i] and words[j] are similar.

Example 1:

Input: words = [ "aba ", "aabb ", "abcd ", "bac ", "aabc "] Output: 2 Explanation: There are 2 pairs that satisfy the conditions: - i = 0 and j = 1 : both words[0] and words[1] only consist of characters 'a' and 'b'. - i = 3 and j = 4 : both words[3] and words[4] only consist of characters 'a', 'b', and 'c'.

Example 2:

Input: words = [ "aabb ", "ab ", "ba "] Output: 3 Explanation: There are 3 pairs that satisfy the conditions: - i = 0 and j = 1 : both words[0] and words[1] only consist of characters 'a' and 'b'. - i = 0 and j = 2 : both words[0] and words[2] only consist of characters 'a' and 'b'. - i = 1 and j = 2 : both words[1] and words[2] only consist of characters 'a' and 'b'.

Example 3:

Input: words = [ "nba ", "cba ", "dba "] Output: 0 Explanation: Since there does not exist any pair that satisfies the conditions, we return 0.

Constraints:

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

    integer :: n, i, j, count
    character(len=100) :: words(100)

    ! read input
    read(*,*) n
    do i = 1, n
        read(*,'(A)') words(i)
    end do

    ! solve problem
    count = 0
    do i = 1, n - 1
        do j = i + 1, n
            if (similar(words(i), words(j))) then
                count = count + 1
            end if
        end do
    end do

    ! print output
    write(*,*) count

contains

    logical function similar(str1, str2)
        implicit none
        character(len=*), intent(in) :: str1, str2
        integer :: i

        similar = .true.
        do i = 1, len(str1)
            if (index(str2, str1(i:i)) == 0) then
                similar = .false.
                exit
            end if
        end do
    end function similar

end program main
❌ Compiled
❌ Executed
❌ Correct 
program similar_strings
implicit none

integer :: i, j, n, count
character(len=100) :: words(100)

! read the number of words
read(*,*) n

! read the words
do i = 1, n
    read(*,*) words(i)
end do

! initialize the count
count = 0

! loop through the words and check for similar pairs
do i = 1, n - 1
    do j = i + 1, n
        if (similar(words(i), words(j))) then
            count = count + 1
        end if
    end do
end do

! print the result
write(*,*) count

contains

! check if two strings are similar
function similar(str1, str2) result(similarity)
implicit none

logical :: similarity
character(len=*), intent(in) :: str1, str2

! initialize the similarity flag
similarity = .false.

! check if the strings have the same length
if (len(str1) /= len(str2)) then
    return
end if

! check if the strings have the same characters
do i = 1, len(str1)
    if (str1(i:i) /= str2(i:i)) then
        return
    end if
end do

! if we reach this point, the strings are similar
similarity = .true.

end function similar
end program similar_strings
🌐 Data from online sources 
def count_similar_pairs(words):
    count = 0
    for i in range(len(words)):
        for j in range(i + 1, len(words)):
            set1 = set(words[i])
            set2 = set(words[j])
            if set1 == set2:
                count += 1
    return count

We will use a nested loop to iterate through all pairs (i, j) such that 0 <= i < j <= words.length - 1. For each pair of words, create two sets containing the constituent characters for each string. To create the sets, use a set object initialized with the characters from the corresponding word. Compare the two sets to see if they are equal. If they are, increment a counter. After iterating through all possible pairs of words, return the counter as the total number of similar pairs.
🌐 Data from online sources 
#include <vector>
#include <string>
#include <unordered_set>

int count_similar_pairs(std::vector<std::string>& words) {
    int count = 0;
    for (int i = 0; i < words.size(); ++i) {
        for (int j = i + 1; j < words.size(); ++j) {
            std::unordered_set<char> set1{words[i].begin(), words[i].end()};
            std::unordered_set<char> set2{words[j].begin(), words[j].end()};
            if (set1 == set2) count++;
        }
    }
    return count;
}

We will use a nested loop to iterate through all pairs (i, j) such that 0 <= i < j <= words.length - 1. For each pair of words, create two sets containing the constituent characters for each string. To create the sets, use a set object initialized with the characters from the corresponding word. Compare the two sets to see if they are equal. If they are, increment a counter. After iterating through all possible pairs of words, return the counter as the total number of similar pairs.