Leetcode 1531 String Compression II | Coding Decoded SDE Sheet
Vložit
- čas přidán 14. 10. 2022
- Here is the solution to " String Compression II" leetcode question. Hope you have a great time going through it.
🎉Question:leetcode.com/problems/string-...
🔴 Connect with me here:
🔅My Linkedin(Sunchit Dudeja): bit.ly/3Qnk0L0
🔅Don't click: bit.ly/32XIXbU
🔅Insta: bit.ly/31TV5ur
🔅 Twitter: / sunchitdudeja
🔅Telegram Link for Chrome: telegram.me/codingdecoded
🔅Telegram Link for phone : t.me/codingdecoded
------------------------------------------------------------------------------------------------------------------------------------------------
Success Stories/Placement Diaries: • Playlist
------------------------------------------------------------------------------------------------------------------------------------------------
Master Data Structures and algorithms 🔽🔽🔽🔽
🔴 Coding Decoded SDE revision Sheet: bit.ly/3MG7d4D
🔥 Coding Decoded Binary Search TreeMap revision Sheet: bit.ly/3kUsiMa
🔥 Coding Decoded Trie revision Sheet: bit.ly/392YOJH
🔥 Coding Decoded Graph SDE sheet: bit.ly/3sfp8H4
🔥 Coding Decoded Stacks/Monotonic Stacks sheet: bit.ly/38tm0Ri
🔥 Coding Decoded Bit Manipulation sheet:bit.ly/3LkVNSe
🔥 Coding Decoded Backtracking SDE sheet: bit.ly/3FCzMwQ
🔥 Coding Decoded DP SDE sheet: bit.ly/38HgY3E
🔥 Coding Decoded Heaps SDE Sheet: bit.ly/3GQqBK7
🔥 Coding Decoded Maps/Sets SDE Sheet: bit.ly/3xfBemu
🔥 Coding Decoded Two Pointer SDE Sheet: bit.ly/3trJCwX
👉 Solution : github.com/Sunchit/Coding-Dec...
🔥🔥🔥🔥👇👇👇 For discussion/feedback/humour/doubts/new openings
Feel free to join discord / discord
🔴 Checkout the series:
👉 Leetcode Interview experiences and tips : • Playlist
👉 Leetcode contests: www.youtube.com?list=PLEI-q7w3s9gRwAEYzYkvVTsYHDi2-ffdL
👉 Leetcode System Design: • System Design
👉 Leetcode LinkedList: • Coding Decoded LinkedL...
👉 Leetcode Stack: • Coding Decoded Stack S...
👉 Leetcode Binary Search: • Coding Decoded BinaryS...
👉 Leetcode Tree: • Coding Decoded Tree Se...
👉 Leetcode Dyanmic Programming: • Coding Decoded Dynamic...
👉 Leetcode Hard: • LeetCode Hard Problems
👉 Leetcode Heap: • Coding Decoded Heap Se...
👉 Building Coding Aptitude: • Building Coding Aptitude
👉 Leetcode Map: • Coding Decoded Map Ser...
👉 Leetcode Two Pointer: • Coding Decoded Two Poi...
👉 Leetcode Backtracking: • Leetcode Backtracking ...
👉 Leetcode Graph Traversal: • Coding Decoded Graph T...
👉 Leetcode Trie: • Coding Decoded Trie Se...
👉 Leetcode Union Find: • Coding Decoded Union F...
👉 Leetcode BFS Graph Problems: • Coding Decoded BFS Ser...
👉 Leetcode Matrix Problems: • Coding Decoded Matrix ...
👉 Leetcode Easy: • Leetcode Easy Problems
👉 Leetcode Bit Manipulation: • Coding Decoded Bit Man...
✨ Hashtags ✨
#CodingDecoded #ProductBased #SoftwareEngineering #FAANGM #FAANG #NSIT #NSUT #engineering #internship #college #Freshers #amazon #apple #coding #algorithms #programming #LearnCoding #CodingPractice #leetcode #college #Jee #engineering #leetcode #UseLeetcodeEffectively #dailychallenge
#CareerSwami #Freshers #lifeatmicrosoft #microsoft #softwareengineering #lifeatoci #ocicompensation #ocisalary #softwareengineeringexperience
#dsa #coding #gate #coding #jeemains #iit #jeemains2022 #inspiration #india #firstvlog #motivation
#dsa #datastructure #dsapatterns #google #amazon #amazonsde #softwareengineering #codinginterview #codinginterviewquestions #binarysearch
#microfrontends #frontenddeveloper #softwareengineer
#recession #layoffs #SoftwareIndustry
amazing explanation
Nice Explanation
chalaki++ :)
Amazing Explanation as always 😁😁
Awesome explanation bro.
Amazing explanation Sunchit, It is very helpful and you explained new concept very beautifully. Thank you.
Amazing amazing just amazing. Thank you so much brother :)
Thanks buddy
How did you come up with the idea to take 11 as frequency cnt
Omg. It's too difficult to understand and Hard to memorize the solution.
I consider it as exception..
Thanks for your effort :)
Can you tell why again you took n+1 in DP Array as it ranges from 1 to 100 means s.length() = n which means For e.g:
if S="aaaa" then n=4 then as first dimension talks about current [idx] then it should be till s.length() which should be n and also why the frequency state the length is taken as 11 ?
I specially logged in my account to comment about his godly explanations.
He explain hard as well as new concepts so nicely 🔥💘
What if string length is greater than 100?
Hi.
Your explanation was amazing, but I have a request for these types of questions could you please show us the recursive code first. This would help to understand the DP concept better.
bhaiya in line number 22
in exclude condition why k is decreasing by 1 ?
Since we are considering that char at that index has been deleted
Bro what extension you are using for dark mode? I am using dark reader but it doesn't look so cool.
Dark reader extension bro!!
Can you please tell what is the mistake in this tabulation approach ? My memoization code is running fine but I am not able to convert it to tabulation approach. If anyone can help please reply. Thanks
class Solution
{
public:
int getLengthOfOptimalCompression(string s, int k)
{
vector dp(k + 2, vector(s.length() + 1, vector(27, vector(101, -1))));
// i for k, j for index, l for previousCharacter and m for previousCount.
for (int i = 0; i < k + 2; i++)
{
for (int j = s.length(); j >= 0; j--)
{
for (int l = 0; l < 27; l++)
{
for (int m = 0; m < 101; m++)
{
if (i == 0)
{
dp[i][j][l][m] = INT_MAX;
}
else if (j == s.length())
{
dp[i][j][l][m] = 0;
}
else
{
int answer = INT_MAX;
answer = min(answer, dp[i - 1][j + 1][l][m]);
if (l + 'a' != s[j])
{
answer = min(answer, 1 + dp[i][j + 1][l][1]);
}
else if (m == 1 || m == 9 || m == 99)
{
answer = min(answer, 1 + dp[i][j + 1][s[j] - 'a'][m + 1]);
}
else
{
answer = min(answer, dp[i][j + 1][s[j] - 'a'][m + 1]);
}
dp[i][j][l][m] = answer;
}
}
}
}
}
return dp[k + 1][0][26][0];
}
};
waht about the case n==100 all chars same and k=2
Still answer is 4
this solution is not considering all cases, what is n=100 and k = 100, then ans = 0, and if n==100 and k == 91, then return will be 2
same code gives tle in cpp i dont know why
Accepted cpp solution: leetcode.com/submissions/detail/823123744/
pass string by reference
@@shivamsinha5554 tried bro
@@swrserwerwr9137 bro my solution got accepted
@@swrserwerwr9137 by passing reference
Leetcode has Dark mode?? Or is it some sort of extension
Try dark reader extension and on leetcode editor settings select monokai theme.
Pls bhaiya take of quality of sound invest some money on good mike hahhah😅
fr bro, I am annoyed at this same tone voice.. makes it so boring
Why is 11 while declaring the array dp [][][][]= [n+1][27][11][n+1]?
string length can go upto 100 (according to constraints). Due to this we have to declare it as [n+1] [27] [101] [k+1]..but
we know that value of freq from 10 to 99 is 2. so we are using a trick as if ( freq >= 10) freq = 10; so We don't need a bigger size dp.