Palindromic Substrings
Take a look at this problem, by LeetCode: https://leetcode.com/problems/palindromic-substrings/description/
Given a string, your task is to count how many palindromic substrings in this string.
The substrings with different start indexes or end indexes are counted as different substrings even they consist of same characters.
Example 1:
Input: "abc" Output: 3 Explanation: Three palindromic strings: "a", "b", "c".
Example 2:
Input: "aaa" Output: 6 Explanation: Six palindromic strings: "a", "a", "a", "aa", "aa", "aaa".
Note:
- The input string length won't exceed 1000.
The brute-force solution would be something like this: you get all the substrings of the original string, which would give you an O(n^2), and then for each one you check whether it is a palindrome or not, hence composing with another O(n) for a grand total of O(n^3). With an n=1000, this will put you in the 1B mark which will certainly timeout (based on LeetCode's constraints).
There is a better approach: go thru each character in the original string (O(n)) and check whether that character is the center of an odd palindrome, or one of the centers of an even palindrome, which gives you another O(n) for a grand total of O(n^2) or in the other of 1M iterations, which is relatively fast.
Best way to accomplish that is by writing a helper method which counts the number of palindromes centered at around a given index (which can actually be an odd or even) using two-pointers approach. Code is below, cheers & cheers!!!! Marcelo
public class Solution
{
public int CountSubstrings(string s)
{
int count = 0;
for (int i = 0; i < s.Length; i++)
count += CountPalindromesFromCenter(s, i, i) + CountPalindromesFromCenter(s, i, i + 1);
return count;
}
private int CountPalindromesFromCenter(string s, int left, int right)
{
int count = 0;
while (left >= 0 && left < s.Length && right >= 0 && right < s.Length && s[left--] == s[right++])
count++;
return count;
}
}
Looks like great minds do think alike :D
ReplyDeleteclass Solution {
private:
int countSubstringsFrom(const string& s, int left, int right) {
int count = 0;
for (; left >= 0 && right < s.size() && s[left] == s[right]; --left, ++right) {
count += 1;
}
return count;
}
public:
int countSubstrings(const string& s) {
int total_count = 0;
for (int middle = 0; middle < s.size(); middle += 1) {
total_count += countSubstringsFrom(s, middle, middle);
total_count += countSubstringsFrom(s, middle, middle + 1);
}
return total_count;
}
};
I'm somewhat surprised that our brute force solution beats more than 80% of other submissions, since I believe there is a faster way to solve it based on some of the ideas from Manacher's algorithm, but perfect is the enemy of good :)
Thanks for a problem!