Unique Length-3 Palindromic Subsequences - Leetcode 1930 - Python
Vložit
- čas přidán 24. 07. 2024
- 🚀 neetcode.io/ - A better way to prepare for Coding Interviews
🐦 Twitter: / neetcode1
🥷 Discord: / discord
🐮 Support the channel: / neetcode
⭐ BLIND-75 PLAYLIST: • Two Sum - Leetcode 1 -...
💡 CODING SOLUTIONS: • Coding Interview Solut...
💡 DYNAMIC PROGRAMMING PLAYLIST: • House Robber - Leetco...
🌲 TREE PLAYLIST: • Invert Binary Tree - D...
💡 GRAPH PLAYLIST: • Course Schedule - Grap...
💡 BACKTRACKING PLAYLIST: • Word Search - Backtrac...
💡 LINKED LIST PLAYLIST: • Reverse Linked List - ...
💡 BINARY SEARCH PLAYLIST: • Binary Search
Problem Link: leetcode.com/problems/unique-...
0:00 - Read the problem
1:40 - Drawing Explanation
8:52 - Coding Explanation
leetcode 1930 - 5809
weekly leetcode contest 249
#palindromic #subsequence #python
Disclosure: Some of the links above may be affiliate links, from which I may earn a small commission. - Věda a technologie
Hi, NeetCode. People only see how good you are at speaking and how you can solve problems, but they don't know how much effort you put in behind. Could you talk about how you learned such knowledge and how you learned to speak out such knowledge?
Dont need to check all 26 characters as we need to match with right at the end. So better to check left only.
res = set()
left = set()
right = Counter(s)
for mid in range(len(s)):
right[s[mid]]-=1
if right[s[mid]] == 0:
right.pop(s[mid])
for c in left:
if c in right:
res.add(c+s[mid]+c)
left.add(s[mid])
return len(res)
I'm learning a lot from your channel! Thanks! :)
You can optimise it further by checking the palindromes for characters on the left only. No need to check for all 26.
for i in range(len(s)):
right[s[i]] -= 1
for char in left:
if char in right and right[char] > 0:
result.add((char, s[i]))
left.add(s[i])
Disagree that this is optimisation, since left set can be way longer than 26 chars, it can have length=N in worst case. So time complexity for this solution O(N^2).
Input range is given as only “a to z” in the question.
@@VaibhavChauhan08 right, then it’s O(26) in worst case, I forgot how set works🤦♂️
Then indeed for you can save some iterations using this trick, especially for short strings or string with small amount of unique chars. 👍
O(N + (char set size)* logN) solution with unordered_map m and binary search for index.
Good explanation! I modified it a little, you only need to keep track of the last index of char. As long as your i is smaller than the last index of the char you can form a palindrome. No need to do the decrement and remove from the map.
Awesome Explanation!
Could you please solve the rest of the questions of today's and yesterday's contest?
It appears easier to use hash map c->list[firstindex, lastindex] since any char in between forms a parlendrome. This method also O(n*26)and passed all tests.
I also did that. This solution seems to overcomplicate things a lot.
Thanks for the solution!!
Very good explanation
first one was very easy, this one was doable but the other two were damn hard :(
Please make a video on the third one...
Idea: We can generate all unique palindromes of length 3 (26*26 of them, as first and last character must be the same) and binary search in s for respective positions of each unique combination (preprocess in O(N), process O(A^2 * log(N)) - A being the alphabet size
Richard Hendricks would be proud of your hash key calculation
Bro can u suggest me some books in data structures and algorithms in python which you use...?
Your idea about dsa is 👌
Note to self: Can have a hashmap on both sides (left / right)
But more Space will be utilised
Is there a reason why you used pop instead of del?
Thank you
Lol. You posted the solution even before the contest was over.😱😱
Last time I was accidentally a couple minutes early, but this time i scheduled it for 9PM so I dont think it was early
@@NeetCode Yes. You posted it just after contest was over. Anyways, thanks for the excellent explanation.
Nice explanation
We can optimize our process by focusing solely on the unique characters present in the left portion, rather than iterating through all characters from 'a' to 'z'.
Another optimization: once res.size() == (char set size)^2, return.
wasted my whole 90 mins for this problem alone
Instead of checking all the 26 characters, you can check all the characters in the left whether they are in the right.. but in worst case, it is going to 26*n
class Solution:
def countPalindromicSubsequence(self, s: str) -> int:
count = 0
for i in range(26):
l, r = s.find(chr(i + 97)), s.rfind(chr(i + 97))
if l != -1 and r != -1:
count += len(set(s[l + 1:r]))
return count
"I think that this will be helpful for all of you. 😊"
this seems really hard for a medium, but maybe im just really tired and my brain isnt working lol
I've written a Java version solution, it seems more complex than python version, hope there's someone help optimize this.
class Solution {
public int countPalindromicSubsequence(String s) {
Set left = new HashSet();
Map right = new HashMap();
Set ans = new HashSet(); // make sure each palindromic string is unique
char[] chars = s.toCharArray();
for (Character ch : chars) { // init right part
right.put(ch, right.getOrDefault(ch, 0) + 1);
}
for (Character ch : chars) {
// remove ch from right
right.put(ch, right.get(ch) - 1);
if (right.get(ch) == 0) {
right.remove(ch);
}
for (char sideChar = 'a'; sideChar
Same O(26*n) Time Complexity but this code is running consistently faster!
# Get index of all occurrences of alphabets
# And use the very ends of each character and see how many unique characters are in the middle
alpha = defaultdict(list)
res = 0
for i in range(len(s)):
alpha[s[i]].append(i)
# alpha.iteritems is at max 26 times
# in between interation is O(n)
# so this is also O(26*n)
for char, charIdxList in alpha.iteritems():
if len(charIdxList)>=2:
#print(char, charIdxList[0], charIdxList[-1])
#what is the length of unique characters between ch
uniqueChar = set()
for j in range(charIdxList[0]+1, charIdxList[-1]):
uniqueChar.add(s[j])
res += len(uniqueChar)
return res