题目

给定一个字符串，找出无序 变形子串对的数目。

Input Format

第一行包含，测试数据的组数。 每组测试数据是在在一行中的字符串。

约束条件

<svg xmlns:xlink="http://www.w3.org/1999/xlink" width="16.596ex" height="3.343ex" style="vertical-align: -1.171ex;" viewBox="0 -934.9 7145.5 1439.2" role="img" focusable="false"><g stroke="currentColor" fill="currentColor" stroke-width="0" transform="matrix(1 0 0 -1 0 0)"><g transform="translate(2480,0)"><text font-family="monospace" stroke="none" transform="scale(71.759) matrix(1 0 0 -1 0 0)">的</text></g><g transform="translate(3090,0)"><text font-family="monospace" stroke="none" transform="scale(71.759) matrix(1 0 0 -1 0 0)">长</text></g><g transform="translate(3699,0)"><text font-family="monospace" stroke="none" transform="scale(71.759) matrix(1 0 0 -1 0 0)">度</text></g></g></svg>

Output Format

对每组测试数据，在一行中输出要求的答案。

Sample Input 0

<pre style="border: none; font-style: inherit; font-variant: inherit; font-weight: 400; font-stretch: inherit; line-height: 20px; font-family: var(--font-family-input); font-size: 14px; margin: 12px 0px 0px; outline: 0px; padding: 20px; vertical-align: baseline; color: var(--color-text-dark); border-radius: 2px; display: block; word-break: break-word; word-wrap: break-word; white-space: pre-wrap; background-image: initial; background-position: initial; background-size: initial; background-repeat: initial; background-attachment: initial; background-origin: initial; background-clip: initial; background-color: var(--color-bg); overflow-x: auto;">2
abba
abcd
</pre>

Sample Output 0

<pre style="border: none; font-style: inherit; font-variant: inherit; font-weight: 400; font-stretch: inherit; line-height: 20px; font-family: var(--font-family-input); font-size: 14px; margin: 12px 0px 0px; outline: 0px; padding: 20px; vertical-align: baseline; color: var(--color-text-dark); border-radius: 2px; display: block; word-break: break-word; word-wrap: break-word; white-space: pre-wrap; background-image: initial; background-position: initial; background-size: initial; background-repeat: initial; background-attachment: initial; background-origin: initial; background-clip: initial; background-color: var(--color-bg); overflow-x: auto;">4
0
</pre>

Explanation 0

The list of all anagrammatic pairs is and at positions and respectively.

No anagrammatic pairs exist in the second query as no character repeats.

Sample Input 1

<pre style="border: none; font-style: inherit; font-variant: inherit; font-weight: 400; font-stretch: inherit; line-height: 20px; font-family: var(--font-family-input); font-size: 14px; margin: 12px 0px 0px; outline: 0px; padding: 20px; vertical-align: baseline; color: var(--color-text-dark); border-radius: 2px; display: block; word-break: break-word; word-wrap: break-word; white-space: pre-wrap; background-image: initial; background-position: initial; background-size: initial; background-repeat: initial; background-attachment: initial; background-origin: initial; background-clip: initial; background-color: var(--color-bg); overflow-x: auto;">2
ifailuhkqq
kkkk
</pre>

Sample Output 1

<pre style="border: none; font-style: inherit; font-variant: inherit; font-weight: 400; font-stretch: inherit; line-height: 20px; font-family: var(--font-family-input); font-size: 14px; margin: 12px 0px 0px; outline: 0px; padding: 20px; vertical-align: baseline; color: var(--color-text-dark); border-radius: 2px; display: block; word-break: break-word; word-wrap: break-word; white-space: pre-wrap; background-image: initial; background-position: initial; background-size: initial; background-repeat: initial; background-attachment: initial; background-origin: initial; background-clip: initial; background-color: var(--color-bg); overflow-x: auto;">3
10
</pre>

Explanation 1

For the first query, we have anagram pairs and at positions and respectively.

For the second query:
There are 6 anagrams of the form at positions and .
There are 3 anagrams of the form at positions and .
There is 1 anagram of the form at position .

Sample Input 2

<pre style="border: none; font-style: inherit; font-variant: inherit; font-weight: 400; font-stretch: inherit; line-height: 20px; font-family: var(--font-family-input); font-size: 14px; margin: 12px 0px 0px; outline: 0px; padding: 20px; vertical-align: baseline; color: var(--color-text-dark); border-radius: 2px; display: block; word-break: break-word; word-wrap: break-word; white-space: pre-wrap; background-image: initial; background-position: initial; background-size: initial; background-repeat: initial; background-attachment: initial; background-origin: initial; background-clip: initial; background-color: var(--color-bg); overflow-x: auto;">1
cdcd
</pre>

Sample Output 2

<pre style="border: none; font-style: inherit; font-variant: inherit; font-weight: 400; font-stretch: inherit; line-height: 20px; font-family: var(--font-family-input); font-size: 14px; margin: 12px 0px 0px; outline: 0px; padding: 20px; vertical-align: baseline; color: var(--color-text-dark); border-radius: 2px; display: block; word-break: break-word; word-wrap: break-word; white-space: pre-wrap; background-image: initial; background-position: initial; background-size: initial; background-repeat: initial; background-attachment: initial; background-origin: initial; background-clip: initial; background-color: var(--color-bg); overflow-x: auto;">5
</pre>

Explanation 2

There are two anagrammatic pairs of length : and .
There are three anagrammatic pairs of length : at positions respectively.

题目解析

与其对其中的每一个字母进行计数，还不如将所有的字母都按顺序排列一遍，然后再比较最后的两个序列是否相同，此思路的实现代码如下,dict[i]*(dict[i]-1)//2 是为了list出来所有组合

Answer

def sherlockAndAnagrams(s):
    count=0
    dict={}
    n=len(s)
    for i in range(n):
        for j in range(n-i):
            sub=''.join(sorted(s[j:j+i+1]))
            try:
                dict[sub]+=1
            except:
                dict[sub]=1
    for i in dict:
        count+=dict[i]*(dict[i]-1)//2
    return count