Skip to content

Latest commit

 

History

History

2168.Unique-Substrings-With-Equal-Digit-Frequency

Folders and files

NameName
Last commit message
Last commit date

parent directory

..
 
 
 
 

2168.Unique-Substrings-With-Equal-Digit-Frequency

从此题的数目局规模上来看,用N^2的时间来遍历所有的substring、并且判断是否符合要求是可行的。但比较难办的是如何判断这些子串是否是unique。因为N^2个字符串会占用N^3的空间,我们无法直接存下所有字符串再去重。

对于判定字符串重复,我们有固定的套路,那就是rolling hash,可以将任意长度的字符串编码为一个整数来存储。本题中需要注意的是,为了避免将"012"和"12"都哈希成同一个编码,我们可以将十进制的编码规则改为十一进制,这样字符0也会被编码。即

for (int j=i; j<n; j++)
  hash = hash * 11 + (s[j]-'0'+1);