LeetCode 2911. Minimum Changes to Make K Semi-palindromes

October 24, 2023

模擬周賽368。這周有事沒參加，結果剛好碰到夠難又剛好會的Q4。
模擬賽做Q124也有200名，虧了一次上分機會。

題目

輸入字串s和整數k，試將s分割成k個子字串，其使得所有子字串滿足半回文的情況下，所需的字母修改次數最小化。

求所需的最少字母修改次數。

注意：

回文指的是一個字串從左到右，與從右到左讀起來相同
如果一個長度為len的字串存在一個滿足1 <= d < len、也滿足len % d = 0 的正整數d，且將所有索引以d取模後將同餘的字元連接成字串，若新連接出的所有字串都是回文，則稱此字串為半回文
例如 “aa”, “aba”, “adbgad” 和 “abab” 是半回文；但 “a”, “ab” 和 “abca” 不是

解法

其實通過率低的主要原因，有一半是題目不清楚所致，另一半是要求很麻煩。

分割成k個子字串、最小修改次數，很容易聯想到dp。但是何謂子回文就很模糊。
首先是 1 <= d < len 這點，隱晦的說這個子字串長度至少為2。
然後 len % d = 0 代表子字串長度為r*d，有d個新連接出的字串長度都是r。

定義dp(i,k)：將s[i,N-1]分割成k個半回文子字串所需要的最少修改次數。
轉移方程式：dp(i,k) = min( dp(j+1,k-1) + cost(i,j) FOR ALL i<j<N )，其中cost(i,j)是s[i,j]滿足半回文的最小修改次數。
base cases：當i=N且k=0時，子字串分割結束，回傳0；若只出現i=N或k=0其一，代表分割不合法，回傳inf。

共有N*k種狀態，各需要轉移N次。
對於i相同，但k不同的情況下，他們共用到數個相同的cost(i,j)，所以cost也可以做記憶化。

cost(i,j)要將s[i,j]視為一個獨立的字串，其長度size=j-i+1，找出可整除size的d，以餘數將字元串接，最後判斷回文修改次數。
對於每個合法的d，都需要遍歷這個長度size的字串一次，每個d複雜度O(N)。
總共有N^2個子字串，每個子字串平均下來有log N個合法的d。

時間複雜度O(N^3 * log N)。
空間複雜度O(N^2)，瓶頸為cost的狀態數。

class Solution:
    def minimumChanges(self, s: str, k: int) -> int:
        N=len(s)
        
        @cache
        def cost(i,j):
            size=j-i+1
            mn_swap=inf
            for d in range(1,size): # d is number of semi-pal
                if size%d!=0:
                    continue
                semi_size=size//d
                cnt=0
                for start in range(d):
                    cs=[]
                    for ii in range(i+start,j+1,d):
                        cs.append(s[ii])
                    for ii in range(semi_size//2):
                        if cs[ii]!=cs[semi_size-1-ii]:
                            cnt+=1
                mn_swap=min(mn_swap,cnt)
            return mn_swap
        
        @cache
        def dp(i,k):
            if i==N and k==0:
                return 0
            if i==N or k==0:
                return inf
            res=inf
            for j in range(i+1,N):
                res=min(res,dp(j+1,k-1)+cost(i,j))
            return res
        
        return dp(0,k)

同樣長度的子字串，合法的d都是一樣的，可以先預處理所有長度所包含的有效d。

預處理過之後，每次計算cost就可以直接拿出有效的d。
再次複習一下，d一定能夠整除大小為size的子字串，最後一步的位置會停在[size-d, size-d+1, …, size-d+(d-1)]。
所以子字串的右邊界會是size-d+offset，其中0<=offset<d。

MX=200
div=[[] for _ in range(MX+1)]
for i in range(1,MX+1):
    for j in range(i*2,MX+1,i):
        div[j].append(i)

class Solution:
    def minimumChanges(self, s: str, k: int) -> int:
        N=len(s)
        
        @cache
        def cost(i,j):
            sub=s[i:j+1]
            size=len(sub)
            mn_swap=inf
            for d in div[size]:
                cnt=0
                for offset in range(d):
                    left=offset
                    right=size-d+offset
                    while left<right:
                        cnt+=sub[left]!=sub[right]
                        left,right=left+d,right-d
                mn_swap=min(mn_swap,cnt)
            return mn_swap
        
        @cache
        def dp(i,k):
            if i==N and k==0:
                return 0
            if i==N or k==0:
                return inf
            res=inf
            for j in range(i+1,N):
                res=min(res,dp(j+1,k-1)+cost(i,j))
            return res
        
        return dp(0,k)

最後改成遞推版本，也把cost提出外面作為公共函數。
只是不知道為啥反而比較慢。

MX=200
div=[[] for _ in range(MX+1)]
for i in range(1,MX+1):
    for j in range(i*2,MX+1,i):
        div[j].append(i)

def get_cost(s):
    size=len(s)
    mn_swap=inf
    for d in div[size]:
        cnt=0
        for offset in range(d):
            left=offset
            right=size-d+offset
            while left<right:
                cnt+=s[left]!=s[right]
                left,right=left+d,right-d
        mn_swap=min(mn_swap,cnt)
    return mn_swap
        
class Solution:
    def minimumChanges(self, s: str, k: int) -> int:
        N=len(s)
        
        cost=[[0]*N for _ in range(N)]
        for i in range(N):
            for j in range(i+1,N):
                cost[i][j]=get_cost(s[i:j+1])
        
        k0=k
        dp=[[inf]*(k+1) for _ in range(N+1)]
        dp[N][0]=0
        for i in reversed(range(N)):
            for k in range(1,k0+1):
                for j in range(i+1,N):
                    dp[i][k]=min(dp[i][k],dp[j+1][k-1]+cost[i][j])
        
        return dp[0][k0]

mocowcow

題目

解法