Transcript:
How’s it going guys today? We’re going to be going over another interview. Question together today. Our question again is on leak code as always, our questions from Amazon and it’s called string progression. All right, guys, before we start our video today. I just want to introduce the sponsor. Rooftop, slushy rooftop slushy is a product that offers an entire suite of services to make sure that you guys are prepared for your fame interviews. My favorite feature that they actually offer is a direct referral to these different fame companies for the average cost of $30 Trying to get an interview at these places is absolutely insane, and nowadays it’s actually statistically harder to get into a place like Facebook or Google than is Harvard, So I definitely think that the average cost of $30 is definitely fair to try and give yourself a chance at getting into that. If you guys are interested in checking out rooftop slushie you can use the link in my description for 10% off your first purchase. I hope that helps you in your java thing, all right, I said today The problem is called string compression. It’s being asked by Amazon right now, and our problem description says, given an array of characters compress it in place, the length after compression must always be smaller than or equal to the original array. Every element of the array should be a character, not an INT of length 1 after you’re done, modifying the input and please return the length of the new array and they want to. It says it’s a fault. Could you solve it using only one extra space? So we can’t store anything in memory, right, We can only use a few different variables, basically no real data structures to try and solve this problem. So, OK, just in a nutshell, right, We’re given some string that’s of length. N And we want to return a string representing the compression of it in place, such that it’s smaller than the length that it was originally given so hopping down to example 1 here. If we were given the array, AABB si si si, we would return to 6 right, and that’s because 6 would be the length of the newly compressed array in place in the actual array would contain a 2 B 2 C 3 and the reason for that is because we’re actually counting the occurrences of each character, right, so a appears twice a a so we say, okay, that’s going to compress to a occurs twice, all right, so we have the character a and then the number of times that it occurred and then the same thing for B Right B occurred and it occurred twice and then C occurred in C Three times, so our array after this would contain these characters in that order and we need return six because that’s the length at a newly compressed array, in example, two here, right, if we were given just a single a, we just output one and the reason for that is because we tried to compress this string using the same process, right a and then the number one meaning that one an a occurred once that would be longer right than the original strings. That’s not a compression, so we just returned one and the value would actually stay the same, right, We wouldn’t do anything to the array itself, So now, in example, three here if we were given the letter. A and then a ton of letter Bs, we would have put four and the reason for that is because our compression would become a they only occurred once right, so we’re not going to compress that. We’re just gonna McCord a a single, a no number as to how many times that occurred because that wouldn’t be a compression and then B, we would say occurred 12 times, right, so we have a 1 followed by a 2 and it tells us since the character a does not repeat, it does not compress, which is why a just occurs here, and then Bbbbbb occurs 12 times, right, so it’s replaced by B 12 and they say notice that each digit has its own entry in the array. Right, so it wouldn’t be a B and then the string 12 would be a B 1 2 where I guess for this for you guys would really be a b12 and then just as a couple notes, it tells us that all characters have an ASCII value in the range 35 to 126 inclusive and that the length of the characters is always between 1 and 1000 OK, so now you guys seem to like the iPad idea, so I’m going to jump back onto the iPad. We’re going to talk through the logic how to solve this problem and then we’re going to go back to leak code and try and code it down in our editor. All right, guys, so now if we had this problem here, This is example 1 just being shown on the iPad. Now, so how would we actually go through the logic of compressing this string? Well, it’s actually not that bad, right. All we really need to do is iterate through the whole string. So we’re gonna have a pointer. I and then we just need to know that for every single character that we’re on. I how many characters following that ice character are the same right, so we’re gonna have a character were. Sorry, a pointer. I that will initially start at 0 and then we’re also gonna have a pointer. J that’s just going to walk forward through our string counting. How many times we see that same character, right, so J would initially point to the first day as well. It’s still the same as the ice pointer right there. The character at the ice pointer. So we’re gonna increment it and go to the next character. Still the same. So now we’re gonna go to the next character, and now it’s not the same right so now we know how many times a has occurred. Right, that’s just going to be. J minus I times so that will tell us how many times it occurred and now we just need to make sure that we place into our return array, right a occurring this amount of times, so we’d say a and then two, right, and then all we have to do is make sure that we move. I to be updated to that new. J so we’re going to keep doing that process. So now we get to the second B, right. J is going to be updated as well. Now we’re gonna walk through again. We’re gonna find the same thing, right. J is eventually going to point to see well. We put that into our array so now we have. B 2 and then we’re gonna do the exact same thing, right. I is again gonna point to this thing again. 2 J is going to be updated. Updated again. We reach the end of the array. So now we put into our array again, How many times we saw C which will be C and now J minus? I will give us 3 so this is what we would return, right. We have 1 2 3 4 5 6 elements, so we’d return 6 as our answer for that example, so now moving on, to example 2 if we were given just the example a write a single a we would just have a write, a would be our answer. That’s what it would be an array and we’d actually return one and the reason for that is because we have I pointing day. J would be pointing to a right then we move. J and it be at the end of the array, then we do. J minus I. And that would equal 1 right 1 Minus 0 is 1 and so our answer would really look something like a 1 but that’s not what we want, right, That’s not shorter than our original. Answer a so you just output 1 here, because that’s something right, so trying to compress. This string is actually not going to help, so we only want to know where we only really want to place this occurrences here Whenever J minus, I is strictly greater than 1 so that’s something that we want to hold on to and remember for our problem. So now if we look at example 3 and this is going to combine different things that we need to know if this was our string right a and then the letter B 12 times, we would do the same process, right, so we’d have Ai starting J starting at a wed move J forward. It’s not the same right so then we’d have J minus I and that equals one, and that’s not strictly greater than one right like we said in the previous problem, so we don’t want to compress that. So so far, we would just have the letter. A in our array in place at the 0th index. Now we’re gonna see B right So I is going to be 1 J is gonna be 1 and then we’re gonna move J right constantly. J is going to move to this B then to this B then to this. Be right all the way to the end of the array and now we’re going to do arithmetic and we’re going to do. J minus I and that’s going to give us 12 so we have a right. We’re not going to put it 1 after it because we said that it’s not strictly greater than 1 so it would just be a then we’d see. B and B occurs 12 times, so we have to place first the 1 as one character, and then we’d have to place the tube, so this would really be 2 separate strings here, right as are all of these different characters here. So if this was our string, we’d output 4 right so now we’ve compressed it to this and we’re actually just going to output the length, so we’d output 4 here, all right, so now let’s start diving into our solution here on the editor, and I hope that walking through those examples on the iPad was helpful, so the first thing we want to do Is we want to keep track of an index, right. We always need to know where to place either that number, or that letter that we’re currently on into our character array that we have sorrines’s a INT index equals 0 and then we also want an integer. I right. We want to have that pointer so that we can walk through our entire string, so I’m gonna say while I is less than characters dot length. Now we want our second pointer, right, we want to have. J That’s initially going to point to odd, and we said that J has to walk forward while it’s equal to the character. That’s at the I position so I could say. Wow, J is less than characters dot length so that we don’t go out of bounds and characters of J is equal to the character at the I position. We just want to increment. J okay, great, So now once we actually have that count, right, this loop will break. Eventually, whether we reach the end of the array where the two characters aren’t the same. So the first thing we want to make sure is we record the character that we just saw right so. I’m going to say, okay, characters of index now. I’m gonna say plus, plus so that we keep moving index forward, so we’re gonna place at the index position. Our eyes character, sometimes a character’s eye. Now what we need to do is. We need to check that if we saw that character strictly more than once, then we need to compress it, right, so if we saw like a three times, we need to make sure we say a three instead of a a a right because that would help us that would compress the string, so we’re gonna say if J minus. I is strictly greater than one. Then we actually have some work to do to make sure that we’re effectively doing that compression. So because that’s actually an integer that we have, right. J minus. I is an integer. I’m just going to turn it to a string called. Count and that’s going to be J minus. I just appended with an empty string, so it converts it to a string now. We want to walk through every character in that account, right, because if character was two digits long or three digits long if something occurred 33 times or 105 times, we had to make sure that we place every character into our character’s array to make sure we’re compressing it correctly so now. I’m gonna say four characters see in count to care array, and I’m going to say characters of index plus plus again just so that we’re walking forward. Equals that character see that we’re home and now, really the last thing we have to make sure we do is every single time We move those pointers, right. I might be here. J is net. Walk all the way to here. I need to make sure that I update I to now point to J. So we started the next character that we haven’t seen, so I’m just gonna say I equals J and then once this loop finishes, right, Hopefully we’d actually compressed everything and all we’ll actually need to do if we did this correctly because return our index because that’s going to represent the new length of the compressed array so now. I just talk quickly about a run time before we submit the solution. Well, what are we really doing? We’re just gonna walk through the entire length of the character’s right, and so even though there’s this nested loop, and it looks kind of scary, right, it’s not really doing anything that’s extra work, right, We’re just walking a pointer further and then we’re moving this pointer to be updated to that pointer. Right, so we’re really only walking through the string once, so I tailor a run time is O of N Where N is number of characters in our string In terms of our space complexity, right, we’re not using add extra data structure. We’re just using a couple simple variables like this. I and J and our count. So I’d say that our space complexity is like they asked over 1 So now let’s run this code, lets. Make sure that it works awesome and it does so guys. That’s how to solve string compression in Java again. This questions being asked by Amazon right now, if you guys enjoyed this video and found it helpful. Do me a favor and leave the video like and subscribe to the channel for more. I’ll see you guys [Music]!