2472. Maximum Number of Non-overlapping Palindrome Substrings

Problem

You are given a string s and a positive integer k.

Select a set of non-overlapping substrings from the string s that satisfy the following conditions:

• The length of each substring is at least k.

• Each substring is a palindrome.

Return **the *maximum* number of substrings in an optimal selection**.

A substring is a contiguous sequence of characters within a string.

  Example 1:

Input: s = "abaccdbbd", k = 3
Output: 2
Explanation: We can select the substrings underlined in s = "abaccdbbd". Both "aba" and "dbbd" are palindromes and have a length of at least k = 3.
It can be shown that we cannot find a selection with more than two valid substrings.

Example 2:

Input: s = "adbcda", k = 2
Output: 0
Explanation: There is no palindrome substring of length at least 2 in the string.

  Constraints:

• 1 <= k <= s.length <= 2000

• s consists of lowercase English letters.

Solution (Java)

class Solution {
    public boolean getLen(int[] Ar, String s, int left, int k)
    {
        // Expanding the boundaries around fixed pivot with given constraints
        while(Ar[0]>=left && Ar[1]<s.length() && s.charAt(Ar[0])==s.charAt(Ar[1]))
        {

            if((Ar[1]-Ar[0]+1)>=k)
                return true;
            Ar[0]--;
            Ar[1]++;
        }
        return false;
    }
    public int maxPalindromes(String s, int k) {

        int left = 0;
        int[] Ar = new int[2];
        int cnt = 0;
        //0-> Left
        //1-> Right
        for(int right = 0;right<s.length();right++)
        {
            boolean isPossible = false;
            Ar[0] = right;
            Ar[1] = right;
            isPossible = getLen(Ar,s,left,k); // For odd length substring
            if(isPossible)
            {
                left = Ar[1]+1;
                cnt++;
            }
            else
            {
                Ar[0] = right;
                Ar[1] = right+1;
                isPossible = getLen(Ar,s,left,k); // For substring of even length
                if(isPossible)
                {
                    left = Ar[1]+1;
                    cnt++;
                }
            }
        }

        return cnt;
    }
}

Explain:

nope.

Complexity:

• Time complexity : O(n).
• Space complexity : O(n).