3138. 同位字符串连接的最小长度

思路

记住一个点即可：由同位字符串组成的字符串，它们排序后是相同的
1.用dict1来记录可能成为同位符的字符串个数以及同位符的使用次数：
从len(s)-1开始遍历，若 len(s)%i == 0:说明组成同位符字符串长度有可能是i,则记录此长度及对应的使用次数（即 len(s）// i )
2.接着根据可能存在的同位符，依次去遍历字符串s：
在遍历过程中如果遇到排序后字符串不相同的情况，说明此此字符串不是同位符，则进行下一个同位符的遍历。
若遍历s后，同位符出现次数==dict1对应同位符次数，则说明此同位符是可以构成字符串的。
若存在多个同位符的情况，则选取字符串长度最小的

时间复杂度: O(n^2)

代码

class Solution:
    def minAnagramLength(self, s: str) -> int:
        t=set(s)
        #同位字符是本身
        if len(s)==len(t):
            return len(s)
        #同位符是一个字符
        if s.count(s[0])==len(s):
            return 1
        #记录可能存在的同位符(位数)及使用同位符次数
        dict1={}
        c=0
        for i in range(len(s)-1,1,-1):
            if len(s)%i==0:
                dict1[i]=len(s)//i
        for i in dict1.keys():
            t=1
            s1=''.join(sorted(s[0:i]))
            for j in range(i,len(s),i):
                if s1==''.join(sorted(s[j:j+i])):
                    t+=1
                else:
                    #只要不等说明此时的字符不是同位符
                    break
            if t==dict1[i]:
                #找到第一个有可能的同位符
                if c==0:
                    c=i
                else:
                    #多个同位符找最小
                    c=min(c,i)
        if c==0:
            #遍历可能的同位符后都不是，则说明自身是同位符
            return len(s)
        else:
            return c