此题感觉比较难.这里,我们约定MissingType表示缺了几种类型的字符(大写,小写,数字),取值范围是[0,3].另外约定change表示我们最终方案里需要替换的次数.deleted表示我们最终方案里需要删除的次数.
当len(s)<6时,需要添加6-len(s)个字符.注意到,此中情况下没有重复序列的问题,并且add的操作同时可以解决MissingType的问题.所以最终答案是max(MissingType,6-len(s))
当6<=len(s)<=20时,只存在MissingType和重复序列的问题,而没有需要删除字符的问题.我们容易计算出最高效的"替换"操作方案,也就是每遇到aaa的情况就将第三个元素替换成别的,计做一次change.这样所需的change是最少.同时,考虑到"替换"也可以解决MissingType的问题.所以最终答案是max(MissingType,change)
当len(s)>20时,会同时存在MissingType,重复序列,删除字符的问题,情况最为复杂.我们慢慢分析.
首先我们考虑最高效的"替换"操作,如前,我们容易计算出所需要的最少的change.完成这套操作之后,消灭了重复序列的问题.
然后考虑字符串过长的问题,共有to_delete个元素需要删除.如果我们简单地再删除这么多字符,总计change+to_delete个操作,这是不高效的.因为我们可以用一些"删除"操作来等效之前的"替换"操作.
举个例子来看,如果...aaa...,我们采用"替换"操作的话,需要一次change(替换最后一个a);而如果我们"删除"最后一个a的话,同样也能使这个字符串合法.所以结论是,我们在这里可以进行一次必要的"删除"操作(为什么说是必要,是因为总共有to_delete这么多元素等待删除),而之前进行的"替换"操作就不必要了,也就是change可以减一.
再举个例子来看,如果...aaaa...,我们采用"替换"操作的话,需要一次change(替换第三个a);而如果我们"删除"两个a的话,同样也能使这个字符串合法.所以结论是,我们在这里可以进行两次必要的"删除"操作,而之前进行的"替换"操作就不必要了,即change同样可以减一.
再举个例子来看,如果...aaaaa...,我们采用"替换"操作的话,需要一次change(替换第三个a);而如果我们"删除"三个a的话,同样也能使这个字符串合法.所以结论是,我们在这里可以进行三次必要的"删除"操作,而之前进行的"替换"操作就不必要了,即change同样可以减一.
以上这些例子说明什么意思?因为删除to_delete个字符是"必选动作",如果我们在做这些必选动作的时候,能够代替掉越多的change的话,那就是最高效的方案.再分析一下,第一个例子代表了连续重复字串长度len%3==0,第二个例子代表了连续重复字串长度len%3==1,第三个例子代表了其他情况.我们在遍历s的时候,可以统计这些情况出现的频次,按照优先级的顺序,每做一次(或者两次,三次)"删除"操作,可以避免一次"替换"操作.
最终的结果就是,总共进行的"删除"操作(deleted),加上没有被抵消的"替换"操作(change).注意,change操作可以抵消MissingType,不够抵消的话,需要额外考虑MissingType的个数.