Hello, LinkedIn community. Today, I participated in Leetcode Biweekly 132 and secured a global rank of 117. Despite facing some unknown error issues from leetcode side, I tackled today's problems with the following approaches: 1. Create a new string, iterate over the given string. If we encounter a digit, we pop the last character of the new string (if not empty) otherwise we add current character to the new string and returned the final string. 2. Let's simulate the first n-1 rounds, starting with 0 and 1. we store the winner of each round and the number of wins of that player. If the number of wins of the current player at any time >= k, that is the answer. Otherwise, observe that after the first n-1 rounds, the player with the maximum skill value would win all remaining rounds, eventually reaching k wins. 3 and 4. Let's build an intuitive dynamic programming solution. For each index, we store k values Dp[i][x], representing the maximum length of a subsequence ending at index i with at most x indices having sub[j] != sub[j+1] in the subsequence. By iterating over all previous indices (j) of the array, we calculate each of dp[i][x] as follows if nums[j] equals nums[i] dp[i][x] = max(dp[i][x],dp[j][x] + 1) else ( it's obvious that as values don't match it incurs us one sub[ind] != sub[ind+1] ) dp[i][x] = max(dp[i][x],dp[j][x-1]+1) now it quite comfortably passes 3rd question limits as TC would be O(n*n*k) To optimise this let's make a key observation dp[i][x] only needs two values to derive it's transitions that is an index having value equal to nums[i] (which takes care of transition dp[i][x] = max(dp[i][x],dp[j][x] + 1) ), which is essentially going to be last index j such that nums[j] == nums [i] and when values doesn't match(for 2nd type of transition) for dp[i][x] we do not require all previous indices , but we only need an index j for each x which gives max value of dp[j][x-1]. How to maintain this max? one more key observation is that if the max index j has value same as nums[i] it won't effect the 2nd type of transition. so we just maintain prefix max of k values till index i-1, where prefix[x] represents max value of all dp[j][x] such that j<i now we are only checking for two indices rather than all previous indices which brings down the TC to O(n*k) which is fast enough for 4th question constraints. You can refer to my solutions here. https://lnkd.in/gP_tfbFQ
Congratulations bro
Nikhil Nallagoni
5mo
Well deserved 👏🏻
CSE || Graduating from RGUKT RK VALLEY || 1700+ rating leetcode ll 2⭐@codechef || Expert@coding ninjas
5mo🔥 That's Great Anna