The naive solution is to check for each substring starting from index i to index j, whether it is a palindrome. This will take up time O(n^3) as identifying each substring i..j takes O(n^2) time and checking palindrome takes O(length of string) = O(j-i+1) time.
Approach 1: Intuitive Recursion
The idea is to imagine each index as the center of the palindrome and try extending to the left and right. We have to check for both odd length palindromes and even length palindromes. For the even length case, we consider index i and i+1 to be the center of the string. If s[i]==s[i+1] then we move on to check s[i-1] and s[i+2] and so on. The odd length case is intuitive.
See this solution by keshavk for pictorial representation.
public class Solution {
int count = 0;
public int countSubstrings(String s) {
if (s == null || s.length() == 0) return 0;
for (int i = 0; i < s.length(); i++) { // i is the mid point
extendPalindrome(s, i, i); // odd length;
extendPalindrome(s, i, i + 1); // even length
}
return count;
}
private void extendPalindrome(String s, int left, int right) {
while (left >=0 && right < s.length() && s.charAt(left) == s.charAt(right)) {
count++; left--; right++;
}
}
}
This takes up only O(n^2) time as extendPalindrome takes O(n) time and we call it on each index.
Approach 2: Dynamic Programming
Let us define a 2D dp array where dp[i][j] represents whether substring from index i to j is a palindrome. Clearly, for all i==j, the string will be a palindrome as it contains only one character. Further, for all i>j, it is an invalid substring as we are assuming that i comes before j. Now, for a substring i..j to be a palindrome, it is mandatory for i+1..j-1 to be a palindrome. Further, s[i] should be equal to s[j]. Hence, dp[i][j] = dp[i+1][j-1] && s[i]==s[j].
Example: aba
0 1 2
a b a
0 a 1 0 1
1 b 1 1 0
2 a 1 1 1
1 represents string is a palindrome or invalid
0 represents not a palindrome
Consider dp[0][1] which represents the substring "ab". Here dp[i+1][j-1] = dp[1][0] = 1 but s[0] != s[1] so it is not a palindrome.
Similarly, dp[1][2] = "ba" is not a palindrome.
Consider dp[0][2] which represents the substring "aba". Here dp[i+1][j-1] = "b" = 1 and s[0] == s[1] = "a" so it is a palindrome.
Since we require dp[i+1][j-1] for the calculation of dp[i][j], we cannot traverse the 2D array normally. We have to traverse along the diagonals. If we try to traverse the first row first, say dp[0][3] for some string “abba”, we’ll need dp[1][2] (“bb”) which won’t be set yet. So we’ll traverse along the diagonals (in the above matrix, we traverse the first diagonal [0,1] -> [1,2] and then the second diagonal [0,2]).
string customSortString(string S, string T) {
vector<int> v(26, 0);
for (char c : T)
v[c-'a']++;
string res = "";
for (char c : S) {
for (int i=0; i<v[c-'a']; i++)
res+=c;
v[c-'a']=0;
}
for (int i=0; i<v.size(); i++) {
if (!v[i])
continue;
for (int j=0; j<v[i]; j++)
res+='a'+i;
}
return res;
}
Time complexity: O(n^2)