Welcome to Subscribe On Youtube
-
/** 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. */ public class Palindromic_Substrings { public static void main (String[] args) { Palindromic_Substrings out = new Palindromic_Substrings(); Solution s = out.new Solution(); System.out.println(s.countSubstrings("aaaaa")); // 15 } class Solution { public int countSubstrings(String s) { int count = 0; // dp[i][j] meaning i-th char to j-th char boolean[][] dp = new boolean[s.length()][s.length()]; for (int i = 0; i < dp.length; i++) { dp[i][i] = true; count++; } // @note: below issue is same direction, aaaa case, 1-st and 4th is valid but not counted // for (int i = 0; i < s.length(); i++) { // for (int j = i + 1; j < s.length(); j++) { // if (j - i == 1) { // case: "aa" // if (s.charAt(i) == s.charAt(j)) { // dp[i][j] = true; // count++; // } // } else { // if (s.charAt(i) == s.charAt(j) && dp[i + 1][j - 1]) { // dp[i][j] = true; // count++; // } // } // } // } // from right to left for (int i = s.length() - 1; i >= 0; i--) { for (int j = i + 1; j < s.length(); j++) { if (j - i == 1) { // case: "aa" if (s.charAt(i) == s.charAt(j)) { dp[i][j] = true; count++; } } else { if (s.charAt(i) == s.charAt(j) && dp[i + 1][j - 1]) { dp[i][j] = true; count++; } } } } return count; } } class Solution222 { public int countSubstrings(String s) { int count = 0; // dp[i][j] meaning i-th char to j-th char boolean[][] dp = new boolean[s.length()][s.length()]; for (int i = 0; i < dp.length; i++) { dp[i][i] = true; count++; } // from left to right for (int i = 0; i < s.length(); i++) { for (int j = i - 1; j >= 0; j--) { if (i - j == 1) { // case: "aa" if (s.charAt(i) == s.charAt(j)) { dp[j][i] = true; count++; } } else { if (s.charAt(i) == s.charAt(j) && dp[j + 1][i - 1]) { dp[j][i] = true; count++; } } } } return count; } } } ############ class Solution { public int countSubstrings(String s) { StringBuilder sb = new StringBuilder("^#"); for (char ch : s.toCharArray()) { sb.append(ch).append('#'); } String t = sb.append('$').toString(); int n = t.length(); int[] p = new int[n]; int pos = 0, maxRight = 0; int ans = 0; for (int i = 1; i < n - 1; i++) { p[i] = maxRight > i ? Math.min(maxRight - i, p[2 * pos - i]) : 1; while (t.charAt(i - p[i]) == t.charAt(i + p[i])) { p[i]++; } if (i + p[i] > maxRight) { maxRight = i + p[i]; pos = i; } ans += p[i] / 2; } return ans; } } -
// OJ: https://leetcode.com/problems/palindromic-substrings/ // Time: O(N^2) // Space: O(1) class Solution { public: int countSubstrings(string s) { int N = s.size(), ans = N; // initially all the single characters are counted for (int i = 0; i < N; ++i) { // odd length for (int j = 1; i - j >= 0 && i + j < N && s[i - j] == s[i + j]; ++j) ++ans; } for (int i = 1; i < N; ++i) { // even length for (int j = 0; i - j - 1 >= 0 && i + j < N && s[i - j - 1] == s[i + j]; ++j) ++ans; } return ans; } }; -
class Solution: def countSubstrings(self, s: str) -> int: t = '^#' + '#'.join(s) + '#$' n = len(t) p = [0 for _ in range(n)] pos, maxRight = 0, 0 ans = 0 for i in range(1, n - 1): p[i] = min(maxRight - i, p[2 * pos - i]) if maxRight > i else 1 while t[i - p[i]] == t[i + p[i]]: p[i] += 1 if i + p[i] > maxRight: maxRight = i + p[i] pos = i ans += p[i] // 2 return ans ############ class Solution(object): def countSubstrings(self, s): """ :type s: str :rtype: int """ n = len(s) ans = 0 for i in range(n): left = right = i while left >= 0 and right < n and s[left] == s[right]: ans += 1 left -= 1 right += 1 left = i right = i + 1 while left >= 0 and right < n and s[left] == s[right]: ans += 1 left -= 1 right += 1 return ans -
func countSubstrings(s string) int { ans, n := 0, len(s) for k := 0; k < n*2-1; k++ { i, j := k/2, (k+1)/2 for i >= 0 && j < n && s[i] == s[j] { ans++ i, j = i-1, j+1 } } return ans } -
/** * @param {string} s * @return {number} */ var countSubstrings = function (s) { let ans = 0; const n = s.length; for (let k = 0; k < n * 2 - 1; ++k) { let i = k >> 1; let j = (k + 1) >> 1; while (~i && j < n && s[i] == s[j]) { ++ans; --i; ++j; } } return ans; };
-
class Solution { public int countSubstrings(String s) { int count = 0; int length = s.length(); for (int i = 0; i < length; i++) { count++; int maxLength = Math.min(i, length - 1 - i); for (int j = 1; j <= maxLength; j++) { if (s.charAt(i - j) == s.charAt(i + j)) count++; else break; } } for (int i = 1; i < length; i++) { int left = i - 1, right = i; if (s.charAt(left) != s.charAt(right)) continue; count++; int maxLength = Math.min(left, length - 1 - right); for (int j = 1; j <= maxLength; j++) { if (s.charAt(left - j) == s.charAt(right + j)) count++; else break; } } return count; } } ############ class Solution { public int countSubstrings(String s) { StringBuilder sb = new StringBuilder("^#"); for (char ch : s.toCharArray()) { sb.append(ch).append('#'); } String t = sb.append('$').toString(); int n = t.length(); int[] p = new int[n]; int pos = 0, maxRight = 0; int ans = 0; for (int i = 1; i < n - 1; i++) { p[i] = maxRight > i ? Math.min(maxRight - i, p[2 * pos - i]) : 1; while (t.charAt(i - p[i]) == t.charAt(i + p[i])) { p[i]++; } if (i + p[i] > maxRight) { maxRight = i + p[i]; pos = i; } ans += p[i] / 2; } return ans; } } -
// OJ: https://leetcode.com/problems/palindromic-substrings/ // Time: O(N^2) // Space: O(1) class Solution { public: int countSubstrings(string s) { int N = s.size(), ans = N; // initially all the single characters are counted for (int i = 0; i < N; ++i) { // odd length for (int j = 1; i - j >= 0 && i + j < N && s[i - j] == s[i + j]; ++j) ++ans; } for (int i = 1; i < N; ++i) { // even length for (int j = 0; i - j - 1 >= 0 && i + j < N && s[i - j - 1] == s[i + j]; ++j) ++ans; } return ans; } }; -
class Solution: def countSubstrings(self, s: str) -> int: t = '^#' + '#'.join(s) + '#$' n = len(t) p = [0 for _ in range(n)] pos, maxRight = 0, 0 ans = 0 for i in range(1, n - 1): p[i] = min(maxRight - i, p[2 * pos - i]) if maxRight > i else 1 while t[i - p[i]] == t[i + p[i]]: p[i] += 1 if i + p[i] > maxRight: maxRight = i + p[i] pos = i ans += p[i] // 2 return ans ############ class Solution(object): def countSubstrings(self, s): """ :type s: str :rtype: int """ n = len(s) ans = 0 for i in range(n): left = right = i while left >= 0 and right < n and s[left] == s[right]: ans += 1 left -= 1 right += 1 left = i right = i + 1 while left >= 0 and right < n and s[left] == s[right]: ans += 1 left -= 1 right += 1 return ans -
func countSubstrings(s string) int { ans, n := 0, len(s) for k := 0; k < n*2-1; k++ { i, j := k/2, (k+1)/2 for i >= 0 && j < n && s[i] == s[j] { ans++ i, j = i-1, j+1 } } return ans } -
/** * @param {string} s * @return {number} */ var countSubstrings = function (s) { let ans = 0; const n = s.length; for (let k = 0; k < n * 2 - 1; ++k) { let i = k >> 1; let j = (k + 1) >> 1; while (~i && j < n && s[i] == s[j]) { ++ans; --i; ++j; } } return ans; };