2472. Maximum Number of Non-overlapping Palindrome Substrings

class Solution {
    public int maxPalindromes(String s, int k) {
        int n = s.length();
        boolean[][] isPalin = new boolean[n][n];
        for (int i = 0; i < n; i++) isPalin[i][i] = true;
        for (int i = 0; i < n - 1; i++) {
            isPalin[i][i + 1] = (s.charAt(i) == s.charAt(i + 1));
        }
        for (int len = 3; len <= n; len++) {
            for (int i = 0; i <= n - len; i++) {
                int j = i + len - 1;
                isPalin[i][j] = (s.charAt(i) == s.charAt(j)) && isPalin[i + 1][j - 1];
            }
        }
        int count = 0;
        int i = 0;
        while (i <= n - k) {
            boolean found = false;
            for (int len = k; len <= k + 1 && i + len - 1 < n; len++) {
                int j = i + len - 1;
                if (isPalin[i][j]) {
                    count++;
                    i = j + 1;
                    found = true;
                    break;
                }
            }
            if (!found) i++;
        }
        return count;
    }
}

class Solution:
    def maxPalindromes(self, s, k):
        n = len(s)

        isPalin = [[False] * n for _ in range(n)]

        for i in range(n):
            isPalin[i][i] = True

        for i in range(n - 1):
            isPalin[i][i + 1] = s[i] == s[i + 1]

        for length in range(3, n + 1):
            for i in range(n - length + 1):
                j = i + length - 1

                isPalin[i][j] = (
                    s[i] == s[j] and
                    isPalin[i + 1][j - 1]
                )

        count = 0
        i = 0

        while i <= n - k:
            found = False

            for length in range(k, k + 2):
                if i + length - 1 >= n:
                    break

                j = i + length - 1

                if isPalin[i][j]:
                    count += 1
                    i = j + 1
                    found = True
                    break

            if not found:
                i += 1

        return count

class Solution {
public:
    int maxPalindromes(string s, int k) {
        int n = s.size();

        vector<vector<bool>> isPalin(n, vector<bool>(n, false));

        for (int i = 0; i < n; i++)
            isPalin[i][i] = true;

        for (int i = 0; i < n - 1; i++)
            isPalin[i][i + 1] = (s[i] == s[i + 1]);

        for (int len = 3; len <= n; len++) {
            for (int i = 0; i <= n - len; i++) {
                int j = i + len - 1;

                isPalin[i][j] =
                    (s[i] == s[j]) &&
                    isPalin[i + 1][j - 1];
            }
        }

        int count = 0;
        int i = 0;

        while (i <= n - k) {
            bool found = false;

            for (int len = k; len <= k + 1; len++) {
                if (i + len - 1 >= n)
                    break;

                int j = i + len - 1;

                if (isPalin[i][j]) {
                    count++;
                    i = j + 1;
                    found = true;
                    break;
                }
            }

            if (!found)
                i++;
        }

        return count;
    }
};

class Solution {
    maxPalindromes(s, k) {
        const n = s.length;

        const isPalin = Array.from(
            { length: n },
            () => Array(n).fill(false)
        );

        for (let i = 0; i < n; i++) {
            isPalin[i][i] = true;
        }

        for (let i = 0; i < n - 1; i++) {
            isPalin[i][i + 1] = s[i] === s[i + 1];
        }

        for (let len = 3; len <= n; len++) {
            for (let i = 0; i <= n - len; i++) {
                const j = i + len - 1;

                isPalin[i][j] =
                    s[i] === s[j] &&
                    isPalin[i + 1][j - 1];
            }
        }

        let count = 0;
        let i = 0;

        while (i <= n - k) {
            let found = false;

            for (let len = k; len <= k + 1; len++) {
                if (i + len - 1 >= n) {
                    break;
                }

                const j = i + len - 1;

                if (isPalin[i][j]) {
                    count++;
                    i = j + 1;
                    found = true;
                    break;
                }
            }

            if (!found) {
                i++;
            }
        }

        return count;
    }
}