Palindromic Substrings
- 2 min read
- LC-Medium
- Dynamic Programming
3 years ago
Solution
- This solution is very similar to the O(n^2) solution in Longest Palindromic Substring, here instead of tracking the longest substring, you just increment a value whenever a valid palindrome is seen
- Remember to check for both odd-length and even-length palindromes
| Time | Space | Explanation |
|---|---|---|
O(n^2) | O(1) |
def countSubstrings(self, s: str) -> int:
ans = 0
for i in range(len(s)):
l = r = i
while l >= 0 and r < len(s) and s[l] == s[r]:
ans += 1
l -= 1
r += 1
for i in range(len(s) - 1):
l, r = i, i + 1
while l >= 0 and r < len(s) and s[l] == s[r]:
ans += 1
l -= 1
r += 1
return ans
Solution (Dynamic Programming)
| Time | Space | Explanation |
|---|---|---|
O(n^2) | O(n^2) |
- Again, exactly the same DP solution as Longest Palindromic Substring
def countSubstrings(self, s: str) -> int:
n = len(s)
dp = [[False] * n for _ in range(n)]
ans = 0
for i in range(len(s)):
dp[i][i] = True
ans += 1
for i in range(len(s) - 1):
if s[i] == s[i + 1]:
dp[i][i + 1] = True
ans += 1
for diff in range(2, n):
for i in range(n - diff):
j = i + diff
if s[i] == s[j] and dp[i + 1][j - 1]:
dp[i][j] = True
ans += 1
return ans