Shifting Letters II - Leetcode 2381 - Python

[@_tym3k]

Who else coming here from the daily question after time limit exceeded?

[@pentosdso3757]

haha yes, me too

[@STACYEMMA-y2e]

Mee😅

[@ajitpalsingh606]

32/39

[@ajaymishra1511]

@@ajitpalsingh606 me

[@staywithmeforever]

I pretty much know brute force gives tle I came directly

[@soupayt]

Hey Neetcode, nice explanation! One suggestion I have is that you mention that this pattern is *Sweep Line* for viewers so they can dig into this pattern more, since its a somewhat frequent pattern for more advanced prefix sum problems. Maybe you could make some videos on the pattern since you seem to have it down (I would recommend Zero Array Transformation I & II since they're Google tagged and relatively simple to understand and visualize). Also I've put my approach to this problem is below and I think its a bit simpler to understand (excluding the character manipulation, but that can be dodged by what you did in the video by converting to integers beforehand) since it doesn't require a reverse traversal and to apply the accumulated diffs to each character in the string! Either way nice work! class Solution: def shiftingLetters(self, s: str, shifts: List[List[int]]) -> str: # Sweep Line! # forward would insert a [+1, -1] and backward inserts a [-1, +1] for the start and end+1 positions. n = len(s) prefixes = [0] * (n + 1) # If the direction is forward, then the start is +1 and end+1 is -1, vice versa if it is backwards. for start, end, direction in shifts: prefixes[start] += 1 if direction else -1 prefixes[end + 1] -= 1 if direction else -1 for i in range(1, len(prefixes)): prefixes[i] += prefixes[i-1] # Now we just apply the shifts we've precalculated to the chars, prefixes[i] holds the offset we want to apply. res = [] for i, char in enumerate(s): new = chr(ord('a') + ((ord(char) - ord('a') + prefixes[i]) % 26)) res.append(new) return "".join(res)

[@NeetCodeIO]

Yeah that's true. Tbh i dont take notes before recording, so i just keep a list of things in my head that I want to cover, so I forget sometimes. Thanks for mentioning it though, comments like these are helpful for others so I appreciate it.

[@sujalsharma5181]

hey @soupayt I see you have a lot of experience solving problems, recognizing patterns ig so if possible can i have your social media (any) or anything through which i can contact you as i m beginner and i need some kind of guidance. Please if you could

[@see7529]

Never in a million years i could have a thought process like this damn

[@swanv951]

Great solution. I spent a lot of time trying to solve it as intervals problem. However, I feel that tracking the range forward instead of backwards is more intuitive. i.e. Store shift [s,e,d] as prefix_diff[s] += d and prefix_diff[e+1] -= d

[@shinsha_]

i was stumped after my first approach got TLE

[@kaseynguyen4983]

Haha same! I even went back to solve Shifting Letters 1 and did it in 5 minutes and was still stuck here

[@toothpicks_96]

same here

[@STACYEMMA-y2e]

32/39😢

[@leechaolan6227]

watched all the videos related to this question ... literally no body made me understand better than you did

[@almagee16]

Question about 18:44 . If there are many shifts to the left, then theoretically the diff could be a very small negative number like -27, right? In that case, if we simply add 26 to it, then try to mod it in a non-Python language, wouldn't we still wind up with a negative number? Instead of simply adding 26 once, should we continuously add 26 until the sum is positive, and then do the modulus operator?

[@sleepypixie8828]

safe to say that this question and its solution deep fried my brain. Might be easy for some to understand this but it took me a long time to even understand this solution

[@VanjeAv]

Love youuu Neeet ❤

[@NeetCodeIO]

love you too

[@VanjeAv]

@@NeetCodeIO made my day!

[@mohaimenchowdhury]

The way you explained Difference Array technique is awesome.

[@business_central]

the prefix trick of today, amazing. I knew Prefix would help but just couldn't figure out how. Thank you as usual Neet for all of these!

[@jamestwosheep]

Thank you so much for the prefix sum explanation! My first attempt involved sorting the shifts and using a min heap, and I was scratching my head wondering why it was so slow compared to all the other sample solutions.

[@shibambiswas]

18:58 special number in Runtime Beats

[@Axel.Blazer]

😋

[@RamCharanKoravi]

please add the thought process like you have done in this video,, it helps me to recheck whether i have thought the same or not

[@orepajic2625]

The TLE solution was pretty easy to come by, but this one was very difficult not gonna lie

[@melvinjoseph4018]

Here's something cool i learnt in python -1%26=25 Never expected this to work, makes it a lot easier

[@tejas1531]

Thanku so much for today's solution

[@blairi]

Great video, Neet! You explained this problem very well-definitely a little tricky one. I was wondering, doesn't this prefix approach have a time complexity of O(n + m)? 13:28

[@igeville21]

Why is the prefix array length s+1 in the example if index 0 is never used?

[@Hoppitot]

Ok but whats the point in complicating it with running it in reverse and having offset positions? I did a similar solution but just set start to +1 and end+1 to -1 (in the case of forward shift). Then they will be mapped directly onto eachother and you can iterate forwards code, 3ms beats 81%, memory beats 78%. If anybody knows how to make it better please tell me. except making the vector +1 length so I dont need to make the if else statement in the first loop. class Solution { public: string shiftingLetters(string s, vector& shifts) { std::vector moves(s.length(), 0); for(const auto &shift: shifts){ if(shift[2]){ moves[shift[0]]++; if(shift[1]+1 < moves.size()) moves[shift[1]+1]--; }else{ moves[shift[0]]--; if(shift[1]+1 < moves.size()) moves[shift[1]+1]++; } } int move = 0; for(int i = 0; i < moves.size(); i++){ move += moves[i]; move = (move + 26) % 26; s[i] = 'a' + (s[i] - 'a' + move+26) % 26; } return s; } };

[@Hoppitot]

fixed the vector length and it runs 0ms

[@120183PAV]

Hey Neet. Thank you for the video. I think that adding 26 to make modulo work in previous languages should happen sooner (when you are making the prefix array). In theory the line "diff + res[i-1] + 26" could still be negative and it would not work in other languages.

[@Reck1025]

In other languages you would just need to mod the diff by 26 since it could be huge.

[@user-my6yf1st8z]

brilliant as always

[@kingdominth4]

Question: is there any reason that you have to traverse right to left? Could you traverse the diff array from the other direction? If you change your mapping scheme -> L=1 & R=-1 (forward) and L=-1 & R=1 (backwards)?

[@thomasngo6650]

Thank you for the clear explanation. I read the editorial solution on Leetcode but found it challenging to grasp the intuition behind the prefix approach. How do you develop insight into this two-prefix method? I tried debugging and printing variables like the difference or prefix array, but it didn’t help much. Do you have any tips for understanding such approaches better?

[@Salehinrafi]

This question should be categorized as "Hard". I bet a few people can come up with this solution without any clues

[@siddhesh119369]

thanks for visual explaination, i was stuck after simulation approach, now learn one more pattern

[@-ArnobBiswas]

I had to do something like while(diff

[@raghavkaul-nm4be]

char shiftChar(char c, int i) { int shift = (c - 'a' + i) % 26; if (shift < 0) shift += 26; char ans = 'a' + shift; return ans; } T_T

[@devnarula6733]

@@raghavkaul-nm4be it's always better to add full code instead of partial code with badly named variables

[@bhavyajainnd]

Beats 69.69% very nice 👌

[@harsh90dem0]

off topic .. are you drawing by using the mouse (cos i can hear the mouse clicks) or are you using a writing tab ?? makes me wonder how difficult it would be to write on screen using the mouse

[@hoangvacban]

you are a genius, thank you, it help me a lot

[@finemechanic]

I wonder what mystery quirk led to this "reverse" solution. My solution is mostly the same, but I add to prefix if direction is 1 and I iterate from 0 to n.

[@luizelias6155]

in python in order to handle negative shifts you don't need to add 26 and then mod the result by 26 as you did. your case example: ( - 1 + 26 ) % 26 = 25 % 26 = 25 how you could have done: -1 % 26 = 25 yes, python handles negative values on mod operations gracefully

[@NeetCodeIO]

Didn't I mention that? I ran the code in the video without the +26 and it also worked.

[@MehmetDemir-xi3yy]

Hey man could you please do a video about segment tree? Like you can solve a lc problem and teach us while you solving. Thanks

[@manimaran3926]

that's freaking genius

[@Entertainmentexe]

Can you make a detailed video on Sweep Line?

[@33_chaitanyagadkari64]

why did you put -1 for 1 on 12:19

[@zweitekonto9654]

video starts at 6:44

[@rajsuriyang3427]

9:20 mind blown.

[@chrisadjei2640]

I paused the video to go and solve Shifting Letters 1 before coming back lol.

[@trueinviso1]

Another algorithm I didn't know, add it to the list

[@yhbarve]

Vamos!

[@gireeswar18]

In the second example, the update was made at index 3, but the left was at index 2 ???

[@STACYEMMA-y2e]

TLE 🧘🏼

[@ramez3038]

is this a common technique or something? cuz i've never seen it and i could never come up with it

[@copilotcoder]

Solved it just now

[@karthi7102]

GOAT GOAT GOAT

[@EranM]

-1%26 also = 25.. :/

[@jp-wi8xr]

class Solution: def shiftingLetters(self, s: str, shifts: List[List[int]]) -> str: cum = [0] * (len(s) + 1) for i, j, d in shifts: if d == 0: d = -1 cum[i] += d cum[j + 1]-= d cur = 0 ans = "" for i in range(len(s)): cur += cum[i] ans += chr(97 + (ord(s[i]) - 97 + cur) % 26) return ans

[@FifaHades]

What a shitty problem (if you have to solve it in O(n)) to get in interview to determine if the candidate is good engineer goddam though great explanation as usual!! If it will help for someone here is simple and EASY brute force solution in kotlin: fun shiftingLetters(s: String, shifts: Array): String { val asciiValues = IntArray(s.length) for(i in s.indices){ asciiValues[i] = s[i].code // init with the input s string the ascii values } for(shift in shifts){ for(index in shift[0]..shift[1]){ if(shift[2] == 1){ asciiValues[index]+=1 if(asciiValues[index] > 'z'.code){ asciiValues[index] = 'a'.code } } else { asciiValues[index]-=1 if(asciiValues[index] < 'a'.code){ asciiValues[index] = 'z'.code } } } } return asciiValues.map { it.toChar() }.joinToString("") }

[@crontsquared230]

Lol wouldn't even remotely think of this solution. I'm gonna take my TLE as a dub 🥲