Leetcode 2472. Maximum Number of Non-overlapping Palindrome Substrings

[Woodyiiiiiii]

这道题一开始我想用贪心的方法去做：遍历字符串，每次遍历中找到当前字符后下一个字符，看是否是回文字符串，是则跳过这个范围，将结果加一。

class Solution {
    public int maxPalindromes(String s, int k) {
        
        Map<Character, LinkedList<Integer>> map = new HashMap<>();
        int n = s.length();
        int start = 0;
        int res = 0;

        if (k == 1) {
            return n;
        }

        // put all the index of the same character into the map
        for (int i = 0; i < n; i++) {
            char c = s.charAt(i);
            if (!map.containsKey(c)) {
                map.put(c, new LinkedList<>());
            }
            map.get(c).add(i);
        }

        while (start < n) {
            char c = s.charAt(start);
            int f = start;
            LinkedList<Integer> linkedList = map.get(c);
            while (!linkedList.isEmpty() && linkedList.peek() <= f) {
                linkedList.poll();
            }

            if (linkedList.isEmpty()) {
                start++;
                continue;
            }

            // find the next index of the same character
            int next = 0;
            for (int i = 0; i < linkedList.size(); ++i) {
                next = linkedList.get(i);
                if (isPalindrome(s, start, next) && next - start + 1 >= k) {
                    start = next + 1;
                    res++;
                    break;
                }
            }

            if (start == f) {
                ++start;
            }

        }

        return res;
        
    }
    
    private boolean isPalindrome(String s, int l, int r) {
        while (l < r) {
            if (s.charAt(l) != s.charAt(r)) {
                return false;
            }
            l++;
            r--;
        }
        return true;
    }
    
}

但显然这个方法不对：

1. 没有先记录回文字符串，作一层缓存，导致循环里面算使得复杂度变高
2. 会破坏下一个可能的回文子字符串，比如"sjbxiufnaanqkwsqswkqrcznzcddhtuhtthuttjfuufjtcfywgecegwyhhnnhtozczirynhhnyrire"，最后的"rir"会被"rynhhnyr"破坏

可以想到DP的方法，因为每一步都是前一步的叠加态。双层循环。

其次，预处理中，可以想到回文字符串有两种形式，一种是偶数形态，另一种是奇数形态，可以以此分两种情况用二位数组进行记录。

class Solution {
    public int maxPalindromes(String s, int k) {

        int n = s.length();
        if (k == 1) {
            return n;
        }

        // cache[i][j] 表示 s[i, j] 是否是回文串
        boolean[][] cache = new boolean[n][n];
        for (int i = 0; i < n; i++) {
            for (int j = i + 1, jj = i; j < n && jj >= 0; j++, jj--) {
                if (s.charAt(jj) != s.charAt(j)) {
                    break;
                } else {
                    cache[jj][j] = true;
                }
            }
            for (int j = i + 2, jj = i; j < n && jj >= 0; j++, jj--) {
                if (s.charAt(jj) != s.charAt(j)) {
                    break;
                } else {
                    cache[jj][j] = true;
                }
            }
        }

        // dp[i] means the max palindrome number of s[0, i - 1]
        int[] dp = new int[n + 1];
        for (int i = 1; i <= n; ++i)  {
            dp[i] = dp[i - 1];
            for (int j = 1; j + k - 1 <= i; ++j) {
                if (cache[j - 1][i - 1]) {
                    dp[i] = Math.max(dp[i], dp[j - 1] + 1);
                }
            }
        }

        return dp[n];

    }
    
}

再细致点，可以继续降低复杂度，贪心每个子字符串，只判断长度为k或者k + 1的回文子字符串的情况。

class Solution {
    public int maxPalindromes(String s, int k) {

        int res = 0;
        int n = s.length();

        for (int i = 0; i < n; ++i) {
            if (isPalindrome(s, i, i + k - 1)) {
                res++;
                i = i + k - 1;
            } else if (isPalindrome(s, i, i + k)) {
                res++;
                i = i + k;
            }
        }

        return res;

    }

    private boolean isPalindrome(String s, int l, int r) {
        if (r >= s.length()) {
            return false;
        }
        while (l < r) {
            if (s.charAt(l) != s.charAt(r)) {
                return false;
            }
            ++l;
            --r;
        }
        return true;
    }
    
}

---

• https://leetcode.com/problems/maximum-number-of-non-overlapping-palindrome-substrings/