To solve this problem, we need to find the maximum number of non-overlapping palindromic substrings of length at least 2 in a given string. The key insight here is to use a greedy approach to prioritize shorter palindromic substrings (length 2 first, then length 3) to maximize the count of non-overlapping substrings.
Approach
-
Greedy Strategy:
- For each position in the string, first check if there is a palindromic substring of length 2 (i.e., consecutive characters are the same). If found, increment the count and move to the next position after the substring.
- If no length-2 palindrome is found, check for a palindromic substring of length 3 (i.e., the first and third characters are the same). If found, increment the count and move three positions ahead.
- If neither is found, move to the next position.
-
Edge Cases:
- If the string length is less than 2, return 0 (since no valid substring exists).
- For strings of length 2, check if both characters are the same (return 1 if yes, else 0).
Solution Code
s = input().strip()
n = len(s)
count = 0
i = 0
while i < n - 1:
if i + 1 < n and s[i] == s[i+1]:
count += 1
i += 2
elif i + 2 < n and s[i] == s[i+2]:
count += 1
i += 3
else:
i += 1
print(count)
Explanation
- Greedy Selection: By choosing the shortest possible palindromic substrings first, we ensure that we use the minimum number of characters per substring, allowing more non-overlapping substrings to be formed.
- Efficiency: The algorithm runs in O(n) time complexity, where n is the length of the string, as each character is processed at most once. This makes it optimal for large input sizes.
This approach effectively maximizes the number of non-overlapping palindromic substrings of length at least 2, ensuring the solution is both correct and efficient.


作者声明:本文包含人工智能生成内容。