647. Palindromic Substrings

nullskill · nullskill · commit a58f1407a8fc · 2023-06-25T13:31:14.000+03:00
diff --git a/lib/src/medium/647.palindromic_substrings/main.dart b/lib/src/medium/647.palindromic_substrings/main.dart
@@ -0,0 +1,30 @@
+/// The time complexity of the `countSubstrings` function is `O(n^2)`,
+/// where `n` is the length of the input string `s`. This is because we
+/// loop over each character in `s` and call the `countPalindromes`
+/// function twice for each character.
+/// The space complexity of the countSubstrings function is `O(1)`
+
+class Solution {
+  int countSubstrings(String s) {
+    int count = 0;
+    for (int i = 0; i < s.length; i++) {
+      count += countPalindromes(s, i, i); // odd-length palindromes
+      count += countPalindromes(s, i, i + 1); // even-length palindromes
+    }
+    return count;
+  }
+
+  int countPalindromes(String s, int left, int right) {
+    int count = 0;
+    while (left >= 0 && right < s.length && s[left] == s[right]) {
+      count++;
+      left--;
+      right++;
+    }
+    return count;
+  }
+}
+
+void main(List<String> args) {
+  print(Solution().countSubstrings('aaa'));
+}
diff --git a/lib/src/medium/647.palindromic_substrings/problem.txt b/lib/src/medium/647.palindromic_substrings/problem.txt
@@ -0,0 +1,25 @@
+647. Palindromic Substrings
+https://leetcode.com/problems/palindromic-substrings/
+
+Given a string s, return the number of palindromic substrings in it.
+A string is a palindrome when it reads the same backward as forward.
+A substring is a contiguous sequence of characters within the string.
+ 
+
+Example 1:
+
+Input: s = "abc"
+Output: 3
+Explanation: Three palindromic strings: "a", "b", "c".
+
+Example 2:
+
+Input: s = "aaa"
+Output: 6
+Explanation: Six palindromic strings: "a", "a", "a", "aa", "aa", "aaa".
+ 
+
+Constraints:
+
+1 <= s.length <= 1000
+s consists of lowercase English letters.
