修改后的有序01串一共只有|S|+1种可能情况:
0000...000
0000...001
0000...011
....
0111...111
1111...111
我们可以枚举最后的有序01串,那么就可以通过逐位比较计算出需要修改的字符数目。复杂度O(|S|^2)。
如果我们通过预处理,计算出初始01串的每个前缀和后缀分别有多少个0,多少个1。那么我们就不用O(|S|)的逐位比较,可以直接根据前缀中1的数目和后缀中0的数目计算出需要修改的字符数目。这样总时间复杂度可以降为O(|S|)。
需要非常熟练的运用for、if和字符串(字符数组)。你可以先写一个程序,输入一个01串,统计它有几个0几个1。然后改成输入2个01串,统计它们之间有几个位置不同(其中一个是0,另一个是1)。最后再完成本题。