hiho一下第229周《Same Letters In A Row》题目分析

9
0

《Same Letters In A Row》题目分析

为了描述方便,我们假设输入的字符串是s。

如果对于一个区间[i, j],可以通过不超过K次交换使得s[i]..s[j]都变成相同字符,我们就称区间[i, j]是可行的;否则称之为不可行的。

我们先考虑这样一个问题:对于给定区间[i, j],如何判断这个区间是否是可行的?

要解决上面的问题,我们可以逐次判断:

区间[i, j]是否可以变成全a? 区间[i, j]是否可以变成全b?... 区间[i, j]是否可以变成全z?

而对于一个确定的小写字符ch,区间[i, j]可以变成全ch的充分必要条件是:

(1)整个字符串s包含至少j-i+1个ch字符

(2)[i, j]区间中的非ch字符不超过K个

于是我们只要知道(1)这个字符串中'a'-'z'的数目,我们用tot[]保存;以及(2)s[i] .. s[j]中'a'-'z'的数目,我们用cnt[]保存。即可在O(26)=O(1)的复杂度判断[i, j]是否可行。

其中tot[]数组可以通过O(|s|)的预处理求出。

此外,我们知道区间的可行性举有某种单调性,即:

(1)如果[i, j]是不可行的,那么[i, j+1], [i, j+2], ... 都是不可行的

(2)如果[i, j]是可行的,那么[i, j-1], [i, j-2], ... 都是可行的

所以我们可以用双指针(滑动窗口)的思路去枚举极大可行区间。这样总共枚举O(|s|)数量的区间,并且当区间改变(从[i, j1]变为[i+1, j2])时,cnt[]数组的变化是均摊O(1)完成的。

总的时间复杂度是O(|s|)的。

0 answer(s)

write answer 切换为英文 切换为中文


转发分享