2472. Maximum Number of Non-overlapping Palindrome Substrings


Problem Description

In this problem, you are given a string s and a positive integer k. Your task is to find the maximum number of non-overlapping substrings you can select from string s where each substring has the following characteristics:

  • Its length is at least k.
  • It is a palindrome (reads the same forward and backward).

A solution set is considered optimal when it contains the greatest number of such palindromic substrings. A substring is defined as a contiguous sequence of characters within the string s.

Intuition

To solve this problem, we need to find a way to efficiently identify all possible palindromic substrings of length greater than or equal to k and choose them in a way that we can maximize the count. The intuition behind the solution is to use dynamic programming to keep track of which substrings are palindromes and then use depth-first search (DFS) to try out all possibilities of selecting non-overlapping palindromic substrings.

Firstly, we use dynamic programming to precompute whether a substring starting at index i and ending at index j is a palindrome. This is done by filling a 2D DP table where dp[i][j] is True if the substring s[i...j] is a palindrome and False otherwise. The table is filled from the end towards the beginning of the string, and we use the property that a substring s[i...j] is a palindrome if s[i] equals s[j] and the substring s[i+1...j-1] is also a palindrome.

Next, we use the DFS approach to explore all possible selections of non-overlapping palindromic substrings. Starting from the beginning of the string, at each character, we have the option to either include it in our selection (if it's the start of a palindromic substring) or to skip it. The DFS search is augmented with a memoization technique to avoid redundant calculations by caching results of subproblems.

In the dfs function, we make a recursive call for every potential start of a palindromic substring of length at least k and compute the maximum number from that starting point. We then take the maximum of the count obtained by including versus excluding the current character. The result of the search for each starting index is stored to avoid redundant calculations for overlapping subproblems.

By using DP and DFS with memoization, we can efficiently explore the optimal selections of non-overlapping palindromic substrings and calculate the maximum count.

Finally, Python's @cache decorator is used to automatically cache the results of the dfs function and dfs.cache_clear() is called at the end to clear the cache, preparing it for fresh use if the same instance of the class is used to solve another problem instance.

Solution Approach

The solution to this problem involves two primary techniques: dynamic programming (DP) and a depth-first search (DFS) with memoization.

First, let's break down the DP part:

  1. We initialize a two-dimensional list dp with dimensions n x n, where n is the length of the string s. This list is initialized with True values since a substring from index i to i is always a palindrome (it's a single character).
  2. Next, we want to fill this dp table with values indicating whether the substring from index i to j is a palindrome. To do this, we iterate over all possible end indices j for a substring, starting from one character beyond the current start index i. We then check if dp[i][j] should be True. A substring s[i...j] is a palindrome if the characters at i and j are equal (s[i] == s[j]) and if the substring s[i+1...j-1] is also a palindrome (dp[i + 1][j - 1] == True).
  3. The DP computation is done in a bottom-up manner, where we start checking palindromes from the end of the string moving towards the beginning. This ensures that when we need to check if s[i+1...j-1] is a palindrome, we have already computed it.

After the DP preprocessing is complete, we move on to the DFS part with memoization:

  1. We define a recursive function dfs(i) that takes a starting index i and returns the maximum number of non-overlapping palindromic substrings we can select starting from that index.
  2. In dfs(i), we initially consider skipping the current character, so we call dfs(i + 1) to see the maximum number of selections if we start from the next character.
  3. We then loop through all end indices j that could potentially form a palindromic substring with the current start index i. The loop starts from i + k - 1, as we need substrings of length at least k. For each of these potential end indices, we check if dp[i][j] is True. If it is, we then realize that we've found a palindromic substring. So, we calculate what the maximum number of remaining selections could be if we started selecting again from after this palindromic substring (j + 1), and add 1 because we're including this new palindromic substring in our selection.
  4. We use a decorator @cache on dfs to memoize the results. This saves a lot of computation time since dfs(i) for a given i will always return the same result.
  5. Our final answer is obtained by calling dfs(0), which attempts to select palindromic substrings starting from the first character of s.
  6. Finally, since Python's function caching retains the values between calls, we call dfs.cache_clear() to clear the memoization cache in case the Solution class is used again on a different input.

By embedding the dynamic programming within a DFS framework and leveraging the power of memoization to avoid recalculating subproblems, the proposed Python solution combats the complexity and ensures maximal efficiency in identifying the optimal selection of non-overlapping palindromic substrings.

💪
Level Up Your
Algo Skills

Example Walkthrough

Let's use a small example to illustrate the solution approach. Suppose we are given the string s = "aabbbaa" and k = 3. We need to find the maximum number of non-overlapping palindromic substrings of length at least 3.

Step 1: Initialize the DP table

We create a DP table dp with the same length as s. For s = "aabbbaa", we'll have a 7x7 table. Initially, dp[i][i] (where i ranges from 0 to 6) is True.

Step 2: Fill the DP table

We fill the DP table in a bottom-up manner. For example:

  • dp[0][2] checks if "aab" is a palindrome. It's not, because 'a' != 'b', so dp[0][2] is False.
  • dp[4][6] checks if "baa" is a palindrome. It's not, so dp[4][6] is False.
  • dp[1][5] checks "abbba", which is a palindrome since 'a' == 'a' and "bbb" is a palindrome, so dp[1][5] is True.

After filling out the DP table, we will have indications for all i, j whether s[i...j] is a palindrome.

Step 3: Depth-First Search with memoization

Now, we start with DFS to find the maximum number of non-overlapping palindromic substrings.

  1. The dfs(0) call represents the search beginning from the start of the string. We can either take the palindrome "aab" starting from index 0 (if it were a palindrome and of length ≥ k), or skip it.
  2. We realize "aab" is not a palindrome, so dfs(1) will be called next, continuing the search from index 1.
  3. When at index 1, the next potential palindromic substring is from index 1 to 5, since "abbba" is a palindrome and of length 5 which is ≥ k. So we consider taking this substring 'abbba' by calling dfs(6).
  4. The dfs(6) now represents the remaining string from index 6, and since it is the last character, it returns 0 because it can't form a substring of length k or more.
  5. Thus, dfs(1) would yield a count of 1 + dfs(6) which is 0, giving us a total of 1. This is the maximum number of non-overlapping palindromic substrings starting from index 1.
  6. No other palindromic substrings of the required length can be found from dfs(2), dfs(3), and so on. Hence, dfs(0) will eventually return 1.

The DFS continues exploring these options, using memoization to store results of previous computations to ensure each unique state is only calculated once.

Final Solution

Finally, the recursive dfs(0) returns 1, as the maximum number of non-overlapping palindromic substrings of length at least 3 that we can select from "aabbbaa" is just 1, which is "abbba". We then clear the cache with dfs.cache_clear() to ensure it doesn't affect subsequent calls if the function were to be reused.

Python Solution

1from functools import lru_cache  # Importing lru_cache for memoization
2
3class Solution:
4    def maxPalindromes(self, s: str, k: int) -> int:
5        # Function to memoize results and avoid redundant calculations
6        @lru_cache(None)
7        def dfs(start_index):
8            # If we have reached beyond the end of the string, no more palindromes can be formed
9            if start_index >= string_length:
10                return 0
11            max_palindromes_from_current = dfs(start_index + 1)
12          
13            # Iterate over all possible substrings starting at index 'start_index'
14            # with minimum length 'k' to find all palindromes
15            for end_index in range(start_index + k - 1, string_length):
16                # If the current substring is a palindrome
17                if dp[start_index][end_index]:
18                    # Choose the max between the current max and 1 plus the number
19                    # of palindromes starting from the end of the current palindrome
20                    max_palindromes_from_current = max(max_palindromes_from_current, 1 + dfs(end_index + 1))
21            return max_palindromes_from_current
22
23        # The length of the input string
24        string_length = len(s)
25        # Dynamic programming table where dp[i][j] will be 'True' if the substring s[i..j] is a palindrome
26        dp = [[True] * string_length for _ in range(string_length)]
27      
28        # Populate the table for substrings of length greater than 1
29        for start_index in range(string_length - 1, -1, -1):
30            for end_index in range(start_index + 1, string_length):
31                # A string is a palindrome if the first and last characters are the same
32                # and the substring between them is a palindrome
33                dp[start_index][end_index] = s[start_index] == s[end_index] and dp[start_index + 1][end_index - 1]
34      
35        # Starting the recursive function from index 0
36        result = dfs(0)
37        dfs.cache_clear()  # Clear the cache before the method exits
38        return result
39

Java Solution

1import java.util.Arrays;
2
3public class Solution {
4
5    private boolean[][] isPalindrome;
6    private int[] memo;
7    private String inputString;
8    private int stringLength;
9    private int minimumPalindromeLength;
10
11    /**
12     * Calculates the maximum number of palindromes that can be formed
13     * from the input string, with each palindrome being at least 'k' characters long.
14     * 
15     * @param s The input string from which palindromes are to be formed.
16     * @param k The minimum length of each palindrome.
17     * @return The maximum number of palindromes of length at least 'k'.
18     */
19    public int maxPalindromes(String s, int k) {
20        stringLength = s.length();
21        memo = new int[stringLength];
22        inputString = s;
23        minimumPalindromeLength = k;
24        isPalindrome = new boolean[stringLength][stringLength];
25      
26        // Initialize the isPalindrome matrix and memo
27        for (int i = 0; i < stringLength; ++i) {
28            Arrays.fill(isPalindrome[i], true);
29            memo[i] = -1;
30        }
31      
32        // Populate the isPalindrome matrix by checking all substrings
33        for (int i = stringLength - 1; i >= 0; --i) {
34            for (int j = i + 1; j < stringLength; ++j) {
35                isPalindrome[i][j] = inputString.charAt(i) == inputString.charAt(j) && isPalindrome[i + 1][j - 1];
36            }
37        }
38      
39        // Begin depth-first search from the first character
40        return depthFirstSearch(0);
41    }
42
43    /**
44     * Depth-first search to find the maximum number of palindromes
45     * from a starting point within the string.
46     * 
47     * @param start The starting index within the input string.
48     * @return The maximum number of palindromes from this starting point.
49     */
50    private int depthFirstSearch(int start) {
51        // If we've reached the end of the string, return 0 since no more palindromes can be formed
52        if (start >= stringLength) {
53            return 0;
54        }
55      
56        // If we have already computed the value for this start index, return it
57        if (memo[start] != -1) {
58            return memo[start];
59        }
60      
61        // Try skipping the current character and see what the result would be
62        int maxPalindromes = depthFirstSearch(start + 1);
63      
64        // Try to find a palindrome starting at this index and see if we can
65        // count more palindromes by including it
66        for (int end = start + minimumPalindromeLength - 1; end < stringLength; ++end) {
67            if (isPalindrome[start][end]) {
68                maxPalindromes = Math.max(maxPalindromes, 1 + depthFirstSearch(end + 1));
69            }
70        }
71      
72        // Store the computed result in the memoization array
73        memo[start] = maxPalindromes;
74        return maxPalindromes;
75    }
76}
77

C++ Solution

1class Solution {
2public:
3    int maxPalindromes(string s, int k) {
4        int length = s.size();
5        // dp[i][j] will be 'true' if the substring s[i..j] is a palindrome
6        vector<vector<bool>> isPalindrome(length, vector<bool>(length, true));
7        // memoization for the results of the recursive calls
8        vector<int> memo(length, -1);
9      
10        // Fill the isPalindrome table
11        for (int i = length - 1; i >= 0; --i) {
12            for (int j = i + 1; j < length; ++j) {
13                // A substring s[i..j] is a palindrome if s[i] == s[j] and
14                // the substring s[i+1..j-1] is also a palindrome
15                isPalindrome[i][j] = s[i] == s[j] && isPalindrome[i + 1][j - 1];
16            }
17        }
18      
19        // Recursive function to find the maximum number of palindromes
20        // starting from index 'start'
21        function<int(int)> findMaxPalindromes = [&](int start) -> int {
22            if (start >= length) return 0; // Base case: reached the end of the string
23            if (memo[start] != -1) return memo[start]; // Return the memoized result
24          
25            // Find the maximum palindromes starting from index 'start'
26            int maxPalindromes = findMaxPalindromes(start + 1); // Exclude the current character
27            for (int end = start + k - 1; end < length; ++end) {
28                // If the substring s[start..end] is a palindrome
29                if (isPalindrome[start][end]) {
30                    // Include this palindrome and move to the next part of the string
31                    maxPalindromes = max(maxPalindromes, 1 + findMaxPalindromes(end + 1));
32                }
33            }
34            memo[start] = maxPalindromes; // Memoize the result
35            return maxPalindromes;
36        };
37
38        // Start the recursion from the beginning of the string
39        return findMaxPalindromes(0);
40    }
41};
42

Typescript Solution

1// This function computes the maximum number of palindromes within a string 's'
2// under the restriction that any palindrome used cannot have a length less than 'k'
3function maxPalindromes(s: string, k: number): number {
4  const length = s.length;
5  // isPalindrome[i][j] will be 'true' if the substring s[i..j] is a palindrome
6  const isPalindrome: boolean[][] = Array.from({ length }, () => Array(length).fill(true));
7  // memo array for memoization of the results of the recursive calls
8  const memo: number[] = Array(length).fill(-1);
9
10  // Fill the isPalindrome table
11  for (let i = length - 1; i >= 0; --i) {
12    for (let j = i + 1; j < length; ++j) {
13      // A substring s[i..j] is a palindrome if s[i] == s[j] and
14      // the substring s[i+1..j-1] is also a palindrome
15      isPalindrome[i][j] = s[i] === s[j] && isPalindrome[i + 1][j - 1];
16    }
17  }
18
19  // Recursive function to find the maximum number of palindromes starting from index 'start'
20  const findMaxPalindromes = (start: number): number => {
21    if (start >= length) return 0; // Base case: reached the end of the string
22    if (memo[start] !== -1) return memo[start]; // Return memoized result
23  
24    // Find the maximum palindromes starting from index 'start'
25    let maxPalindromesResult = findMaxPalindromes(start + 1); // Exclude the current character
26    for (let end = start + k - 1; end < length; ++end) {
27      // If the substring s[start..end] is a palindrome
28      if (isPalindrome[start][end]) {
29        // Include this palindrome and move to the next part of the string
30        maxPalindromesResult = Math.max(maxPalindromesResult, 1 + findMaxPalindromes(end + 1));
31      }
32    }
33    memo[start] = maxPalindromesResult; // Memoize the result
34    return maxPalindromesResult;
35  };
36
37  // Start recursion from the beginning of the string
38  return findMaxPalindromes(0);
39}
40

Time and Space Complexity

Time Complexity

The time complexity of the given algorithm can be broken down into two parts:

  1. Constructing the Dynamic Programming Table (dp):

    • The table dp is a 2D array that is used to check if a substring s[i:j+1] is a palindrome.
    • Filling each cell of this table requires checking if the characters at the i-th and j-th positions are equal, and if the substring between these characters (i.e., s[i+1:j-1]) is a palindrome, which has already been computed.
    • There are n rows and, on average, n/2 columns to fill (since we only consider j > i). This results in a complexity of O(n^2) to fill the entire table.
  2. The Depth-First Search (dfs) Function:

    • The dfs function explores all possible palindromic substrings of length at least k.
    • In the worst case, every possible starting position i could yield a palindrome, and thus the dfs function would be called for every other index in the string, resulting in at most O(n) calls to dfs from every position.
    • The memoization via @cache decorator ensures that each state of the dfs function is only computed once. There are n states corresponding to each starting index i. Each state might make a call to the next index j + 1 at most n times leading to a complexity of O(n^2) for the DFS with memoization.

Therefore, the time complexity of the entire algorithm is O(n^2).

Space Complexity

The space complexity is also determined by two factors:

  1. Dynamic Programming Table (dp):

    • The dp table is an n x n matrix, so it takes O(n^2) space.
  2. Depth-First Search (dfs) and Cache:

    • The dfs function is recursive and could potentially go n levels deep in the case of a sequence of palindromic substrings, e.g., a string made entirely of the same character. Thus it could use O(n) stack space.
    • The cache for dfs will store at most n states; since the state is determined by the starting index i only, and we're storing the maximum number of palindromes from that index. Each cached value is an integer, so the overall space taken by the cache is O(n).

Adding O(n^2) for dp and O(n) for dfs stack and cache, the space complexity remains O(n^2).

Overall, the time complexity of the algorithm is O(n^2), and the space complexity is O(n^2).

😈
Become an
Algo Monster

Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.


TA 👨‍🏫