647. Palindromic Substrings
Explanation
To solve this problem, we can iterate through each character in the string s and treat it as the center of a palindrome. We expand outwards from each center to check for palindromic substrings. There are two cases to consider:
- Palindromes with single center (e.g., "aba")
- Palindromes with double center (e.g., "abba")
By considering both cases, we can count all palindromic substrings in the given string.
Algorithm:
- Initialize a count variable to store the total count of palindromic substrings.
- Iterate through each character in the string s: a. For each character, consider it as the center of a palindrome and expand outwards to count palindromes with a single center. b. Also, consider this character and its right neighbor as the double center of a palindrome and expand outwards to count palindromes with a double center.
- Return the total count of palindromic substrings.
Time Complexity:
The time complexity of this algorithm is O(n^2), where n is the length of the input string s. This is because we expand around each character in the string to find palindromic substrings.
Space Complexity:
The space complexity of this algorithm is O(1) as we are not using any extra space proportional to the input size.
class Solution {
public int countSubstrings(String s) {
int count = 0;
for (int i = 0; i < s.length(); i++) {
count += countPalindromes(s, i, i); // single center palindromes
count += countPalindromes(s, i, i + 1); // double center palindromes
}
return count;
}
private int countPalindromes(String s, int left, int right) {
int count = 0;
while (left >= 0 && right < s.length() && s.charAt(left) == s.charAt(right)) {
count++;
left--;
right++;
}
return count;
}
}Code Editor (Testing phase)
Improve Your Solution
Use the editor below to refine the provided solution. Select a programming language and try the following:
- Add import statement if required.
- Optimize the code for better time or space complexity.
- Add test cases to validate edge cases and common scenarios.
- Handle error conditions or invalid inputs gracefully.
- Experiment with alternative approaches to deepen your understanding.
Click "Run Code" to execute your solution and view the output. If errors occur, check the line numbers and debug accordingly. Resize the editor by dragging its bottom edge.