You are given a string s and an integer k. Choose the maximum possible number of non-overlapping substrings such that every chosen substring is a palindrome and has length at least k.
A palindrome is a string that reads the same from left to right and from right to left.
The chosen substrings do not need to cover the entire string. Characters between chosen substrings and any remaining characters may be ignored.
Return the chosen palindromic substrings as a List<String>. The substrings must be returned in the same left-to-right order in which they appear in s.
If there are multiple ways to choose the maximum number of valid substrings, choose the result with the lexicographically smallest sequence of starting indices. If multiple results have the same sequence of starting indices, choose the result with the lexicographically largest sequence of ending indices.
In other words, among all selections containing the maximum possible number of substrings, first compare their complete sequences of starting indices and choose the lexicographically smallest one. If multiple selections have the same complete sequence of starting indices, compare their ending indices from left to right. At the first position where they differ, prefer the selection having the larger ending index.
Method Signature
List<String> maximumNonOverlappingSubstrings(String s, int k)
s is the input string.k is the minimum allowed length of each chosen substring.- Each returned substring must be a palindrome.
- Each returned substring must have length greater than or equal to
k.
- No two returned substrings may overlap in
s.
- The returned substrings must appear in left-to-right order from the original string.
- The returned list must contain the maximum possible number of valid substrings.
- Starting and ending indices are zero-based.
- Ending indices are inclusive.
Constraints
1 ≤ s.length() ≤ 100,0001 ≤ k ≤ s.length()s contains only lowercase English letters.
Examples
Example 1
maximumNonOverlappingSubstrings(s = "abaccdbbd", k = 2)
Output: ["aba", "cc", "dbbd"]
Explanation: The substrings "aba", "cc", and "dbbd" are non-overlapping palindromes, and each has length at least 2. It is not possible to choose more than three valid substrings. The selection ["aba", "cc", "dbbd"] has the starting-index sequence [0, 3, 5]. Another valid selection, ["aba", "cc", "bb"], has the starting-index sequence [0, 3, 6]. Since [0, 3, 5] is lexicographically smaller than [0, 3, 6], ["aba", "cc", "dbbd"] is returned.
Example 2
maximumNonOverlappingSubstrings(s = "abacdcaba", k = 3)
Output: ["aba", "cdc", "aba"]
Explanation: The string contains three non-overlapping palindromes of length at least 3. It is not possible to choose more than three valid substrings.
Example 3
maximumNonOverlappingSubstrings(s = "abcdef", k = 2)
Output: []
Explanation: The string does not contain any palindromic substring of length at least 2.
Example 4
maximumNonOverlappingSubstrings(s = "aaaaa", k = 2)
Output: ["aa", "aaa"]
Explanation: At most two valid non-overlapping palindromic substrings can be chosen. The selections ["aa", "aaa"] and ["aaa", "aa"] have starting-index sequences [0, 2] and [0, 3], respectively. Since [0, 2] is lexicographically smaller, a selection starting at indices [0, 2] is preferred. The selections ["aa", "aa"] and ["aa", "aaa"] both have the starting-index sequence [0, 2]. Their ending-index sequences are [1, 3] and [1, 4], respectively. Since [1, 4] is lexicographically larger, ["aa", "aaa"] is returned.
Example 5
maximumNonOverlappingSubstrings(s = "abcba", k = 4)
Output: ["abcba"]
Explanation: The entire string is a palindrome of length 5, which is greater than the minimum required length 4.