Yes but I am sometimes not even able to understand the solution. Who should I ask in these cases and where? Thanks

But my question is with this DP approach we are only considering:

DP[i][j] being max score of subarray Arr[i, j] so why are you assuming anything outside this subarray exists? Isn't the whole point of DP to just focus on the subproblems?

Yes, sorry about that

Thanks, but I am really struggling with this problem because of multiplication and division mixed with add/sub. Can you help me here?

For this test case "100000000/1/2/3/4/5/6/7/8/9/10"

The order of division is to be from the right to the left, and while just switching for(i in [l, r)) to for(i in [r - 1, l]) works, it causes stackoverflow for large inputs (ie strings of length 300000.

Any way to get around it?

I was hoping to know the stack solution.

Got it using help and skimming over solution

class Solution {
    List<String> sol = new ArrayList<>();
    String s;
    
    public List<String> addOperators(String num, int target) {
        char [] arr = num.toCharArray();
        this.s = num;
        helper(arr, 0, "", 0l, 0l, (long) target);
        return sol;
    }
    
    public void helper(char [] arr, int index, String acc, long prev, long cur, long target){
        if(acc.equals("1+2*3*4")){
            System.out.println(cur);
        }
         if(index >= arr.length){
             if(target == cur){
                 sol.add(acc);
             }
             return;
         }
        
         for(int i = index; i < arr.length; ++i){
             String str = s.substring(index, i + 1);
             if(isInvalidZero(str)) return;
             long curLong = getLong(str);
             
             if(index == 0){
                 helper(arr, i + 1, str, curLong, curLong, target);
             } else {
                 helper(arr, i + 1, acc + '+' + str, curLong, cur + curLong, target);
                 helper(arr, i + 1, acc + '-' + str, -1*curLong, cur - curLong, target);
                 helper(arr, i + 1, acc + '*' + str, prev*curLong, cur - prev + prev*curLong, target);
             }
             
             
         }
    }
    
    public boolean isInvalidZero(String s){
        return (s.isEmpty() || (s.length() > 1 && s.charAt(0) == '0'));
    }
    
    public long getLong(String s){
        return Long.parseLong(s);
    }
}

What an amazing problem. Since I did not get it from this website, how difficult would this be on here?

Div1-C?

Ah dammit, you finding this "straightforward," is pretty dis-heartening. I'm kind of disappointed I couldn't come up with this.

How do you come up with solutions like this? Ie, how did you think of this?

Thanks!

Can you explain this part: "However, if no element of A is bigger than the biggest element of B, you should just use your lowest element, so that you won't "waste" your bigger elements." ?

I don't understand how you came up with this or why its true.

Thanks

Thanks! And what is your technique to come up with greedy strategy?

I am working on this: My blog post

For this one for example I can't come up with a greedy strategy.

How do you think of one for arrays like this for example?

Can you give your recommendation? You seem experienced, any advice is appreciated!

Does anyone have good resources that helped them with Greedy and finding patterns for Greedy problems?

Thanks

Ah I see.

So basically what you are saying is, for problems involving Greedy the best (without proof and during contest) I can do is guess a strategy using test cases and pray that it works?

How exactly do guess the strategy? Is it just trying to draw patterns from examples? Any concrete techniques for that?

Hey!

Ok I am starting to understand it, please tell me if this is correct: By subsequence below I mean palindromic subsequence

Case S[l] == S[r]: - You have 1 subsequence = "S[l]S[r]" - You will add subsequences from S[l, ... , r — 1] --> Call this A - you will add subsequences from S[l + 1, ... , r] --> Call this B Now is the tricky part: Both A and B contain subsequences from S[l + 1, ... , r — 1], so you are counting it twice, but say the subsequence for S[l + 1, ... , r -1] = Y

Then since you counted twice:

• 1 count for just Y
• 1 count for S[l]YS[r] which is also palindromic

So that's why I don't do - sol(l + 1, r - 1)

Final sum is:

1 + sol(l, r - 1) + sol(l + 1, r)

Is this accurate?

Hi, I am not sure I understand why that is the case, please help me here.

If S[l] == S[r] then

I am doing: 1 + sol(s, l + 1, r) + sol(s, l, r - 1) - sol(s, l + 1, r - 1) because

The 1 means the palin. subsequence "S[L]S[R]" (just 2 letters)

The sol(l + 1, r) will cover palin. subseq from S[l + 1, ... , r] and

The sol(l, r - 1) will cover palin. subseq from S[l, ... , r - 1]

But both of these will cover palin. subseq from S[l + 1, ... , r - 1]

So why shouldn't I subtract sol(s, l + 1, r - 1) once?

Thanks!

Can you explain why the greedy strategy works for the case with no zeros?

I was thinking of removing largest digit in every iteration, O(N^2) time, it seems yours is O(N)

Can you help me with DFS approach in O(N)? I am very confused how to do it. Thank you so much

Can you help me out with this DFS approach? I am trying to understand it properly. Say I do a DFS from Node X to all of its children, then if denote:

DP[x][some child] = DP[some child][x] = distance from X to some Child, which ever child we are looking at.

Are you saying I should then use DP[x][some child] for parents of node X?

Thanks!

Hi, I am not sure I understand your hint.

If I know the sum of distances node X to node Y I am not sure how this helps? Thanks!

I've solved it already, the optimization was just a 2d memo :(

anyway, constraint was

ring.length() <= 100 key.length() <= 45

Hey there,

Thanks for the reply and solution. Would you be willing to share why you thought of these things so I can get an idea of your thought process and apply it to future problems?

Thanks

It turns out there is an O(N) solution, can anyone give some hints for that?

How about the case with negative numbers?

If there were no zeros (and only positive numbers) I would basically cut everytime I got (SUM_OF_ARRAY/3).

But with {-1, +1} somewhere there this will make things tricky.

Amazing explanation, thank you so much!

Hi there,

"If some subarray has sum equals to X, it means that if you flip this subarray, you get X 1's more than your initial answer. So, with this information, the answer is related with the maximum subarray sum you can get."

Can you please explain why this is the case? Thank you very much

Auto comment: topic has been updated by aakarshmadhavan (previous revision, new revision, compare).

Can someone please help out with Problem C?

Thanks! I don't see a way to start. The tag said "SORTING," but I am not sure how to even apply it here.

Chill bro lol.

I have a question.

Let's say I give up in 2-3 hours and look at the solution, what am I supposed to learn?

For example, sometimes I'll read the solution, think I've understood the technique then fail some other similar problem.

In other words, how do you learn the fundamentals/techniques underlying in the problem that you can apply to other problems later on?

Hey there,

Thanks for the reply. I'm actually trying to learn how to approach these types of problems. I have done several DP problems on Leetcode OJ, and they are often

dp[i] = maximum sum ending at index i
dp[i] = maximum "whatever" _until_ index i
dp[i][j] = true if S[0, i] == T[0, j]
dp[i][j] = Length of palindromic string starting at index i and ending at index j

I am not sure how you came up with your idea of: dp[i][j] — minimum length of a substring of S which starts in i and has T[j..len(T) - 1] as a subsequence.

Can you please explain your thought process here?

Thanks very much.

Hi there,

Thanks for the reply. I implemented this solution, but it is a slow solution.

Apparently there is a faster DP state for this than using LCS. Any ideas on how to approach that? I am unable to figure it out. Here is the actual problem: https://leetcode.com/problems/minimum-window-subsequence/description/

Thanks

Amazing sheet for those under 1700 such as myself looking to crack interviews and slowly get ot blue rating. Thanks!

Hey there! I am also very stuck on this problem and your solution is not making sense to me. I have some questions, hope you will answer.

-- If C[ a[] % m ] is full, how do you decide the next bucket in the container? Why do you add a[i] number of steps?

-- At the end how do you track what the final array is?

Thanks

Hello! Can someone help me with Problem D? I saw the comment, but I do not understand it. Will appreciate if someone can explain the idea and how you reached it.

For Problem D, I did a BFS from the initial array until one array suceeds. This I feel is correct, but I had a memory limit exceeded within test 5.

Thanks