Unique Length-3 Palindromic Subsequences
- 2 min read
- String
- LC-Medium
3 years ago
Solution
- For a 3 length palindrome, the middle character doesn't matter, and the first and last character should be the same. So we have limited choices. At most, there can be 26^2 palindromes, because we only have 26 choices for the left and right characters, and 26 choices for the middle character.
- Iterate through every character (starting from index 1 till one character before the length)
- Maintain a hashmap which contains all the characters that exist before the current index and after, with their counts
- For a particular character, iterate through all 26 lowercase alphabets
- if there exists an alphabet in both the left and right hashmaps, it means we can form a valid palindromic subsequence, because remember, it's a subsequence and not a substring, which means we can skip characters in between
- Of course, this means you'll have to iterate through the entire string once to build the initial right hashmap.
- As we're iterating, we'll need to remove and add characters to the left and right hashmaps
- Some clever indexing values will have to be used, but these are intuitive.
| Time | Space | Explanation |
|---|---|---|
O(26 * n) | O(26) |
def countPalindromicSubsequence(self, s: str) -> int:
palindromic_subsequences = set()
left_chars, right_chars = defaultdict(lambda: 0), defaultdict(lambda: 0)
left_chars[s[0]] += 1 # Because we're starting from 0
# Take counts of characters to right of index from where we start from.
for i in range(2, len(s)):
right_chars[s[i]] += 1
for i in range(1, len(s) - 1):
for j in range(26):
alphabet = chr(j + ord('a'))
if alphabet in left_chars and right_chars[alphabet] > 0:
palindromic_subsequences.add(f'{alphabet}{s[i]}{alphabet}')
left_chars[s[i]] += 1
right_chars[s[i + 1]] -= 1
return len(palindromic_subsequences)
TLE Backtracking Solution
def __init__(self):
self.palindromic_subsequences = set()
def is_palindrome(self, substr):
return len(substr) == 3 and substr[0] == substr[2]
def depth_first_search(self, s, i, substr):
if len(substr) > 3:
return
if i == len(s):
if self.is_palindrome(substr):
self.palindromic_subsequences.add(substr)
return
self.depth_first_search(s, i + 1, substr)
self.depth_first_search(s, i + 1, substr + s[i])
def countPalindromicSubsequence(self, s: str) -> int:
self.depth_first_search(s, 0, '')
return len(self.palindromic_subsequences)