FastPrep

Description

Solutions

TikTok Twin Pairs

📚RELATED PROBLEMS

The TikTok development team is working on a feature to help creators come up with better captions for their videos. TikTok's algorithm favors engaging captions, so you are building an AI tool that paraphrases captions to make them catchier.

However, TikTok charges creators based on the number of characters that get changed after paraphrasing. Therefore, you are tasked with reducing TikTok creators' costs by identifying 'twin-strings' from the captions to avoid paraphrasing the same content multiple times.

Two strings are considered as 'twin-strings' if they are composed of the same characters, regardless of their arrangement or frequency.

For example, "viral" and "rival" are 'twin-strings' since both are composed of the same five characters: 'v', 'i', 'r', 'a', and 'l'. However, "viral" and "trendy" are not 'twin-strings' since they do not share all the same letters.

Given an array of n strings, determine the number of pairs (i, j) such that 0 ≤ i < j < n and (words[i], words[j]) are 'twin-strings.'

Note: Each string is composed of lowercase English characters only.

Function Description

Complete the function countTwinPairs in the editor.

countTwinPairs has the following parameter(s):

string words[n]: an array of n strings

Returns

long: the number of valid pairs of 'twin-strings' in the given array.

Example 1:

Input:  words = ["abca", "abaa", "baab", "cba"]
Output: 2 
Explanation:

Strings "abca" and "cba" are 'twin-strings' because they are made up of the same characters: 'a', 'b' and 'c'.

Strings "abaa" and "baab" are 'twin-strings' because they are made up of the same characters: 'a' and 'b'.

Thus the pairs (0, 3), (1, 2) are the only valid pairs counted in the answer. Thus the answer is 2.

Example 2:

Input:  words = ["apple", "apel", "silent", "listen", "papel"]
Output: 4 
Explanation:

Note the following case:

Strings "apple", "apel" and "papel" are made up of same unique characters: 'a', 'p', 'e' and 'l'. Thus, any pair of them forms a "twin-string".

Strings "silent", "listen" are also "twin-string" because they are made up of the same unique characters: 'l', 'i', 's', 't', 'e' and 'n'.



Thus, there are 4 such pairs that satisfy the condition 0 <= i < j < n and (words[i], words[j]) are "twin-string." Therefore, the answer is 4.

Constraints:

1 ≤ n ≤ 10^5

The sum of the lengths of all strings does not exceed 10^6

All strings consist of lowercase English characters only.