Interview Question: String Compression

[@martincopes3818]

13:55 This algorithm does not run in linear time, it actually has a quadratic runtime complexity. Since Strings in Java are immutable, concatenation using the + operator takes linear time because it has to copy the whole string. A more efficient solution would be using the StringBuilder class to build the output. Appending to a StringBuilder has an amortized runtime of O(1), thus achieving an overall linear complexity.

[@ByteByByte]

Yes I should have specified that a string builder would be better. Generally it's not necessary to actually use a string builder in your interview solution as long as you make it clear to you interviewer that that is what you would do in production code. I find string builders overcomplicate interview solutions with no real benefit

[@Grassmpl]

or if your not familiar with string builder, you can use java.util.LinkedList out, then return new String(out);

[@srivastava_prateek]

Same was i thinking

[@BRUCE59468]

Yes but most compilers will optimize this.

[@baichen6449]

if I use a stringbuilder what is the space complexity? will it be O(n)?

[@josiegeng7969]

Very nice and clear explanation! Can you pls do an in-place version of it? Using O(1) space.

[@ByteByByte]

Not really sure what you're asking. There's no such thing as an in place string modification in java because strings are immutable

[@fredianriko5648]

Hey thanks for the solution discussions, i got the same question but with added complexity, which the questions have a possibility to generate input of combination with of different characters, such as “abcabcancdddcadb” the question expected to return “2abcancdddcadb” , or “abcabcanc3dadb”, also the questions is required for me to return the shortest compressed string possible, which trifling me by the complexity. By any chance could you please discuss it? Thanks

[@angelurmasekur]

Is this a more efficient solution than maintaining a 256 int array, where each index represents the unicode value of a char. Running a for loop over the initial string and incrementing the int count at each char's index value. Then a separate for loop over the array, where if int > 0, get the char value of the index and the value at that position and append it to a stringBuilder/string? Then in the end, do the same ternary statement you have to return the shorter string

[@ramyaby977]

Great solution, thank you so much

[@fxsabreu]

Nice video, nice series, nice explanation. Keep up the good work!

[@omnnnooy3267]

Amazing series!! Thank you so much

[@ByteByByte]

Thanks!

[@tanzeelrana7348]

What about string "abb" ?

[@praneethaluru2601]

Good point mentioned at 5:49

[@fetchjim]

If the input string s is empty the line "out = out + s.charAt(s.length() - 1) + sum" will try to reference the character of s at index -1, which will result in an IndexOutOfBoundsException. There could be a check at the beginning of the function to return "" if s is empty.

[@ByteByByte]

yeah that's probably the simplest fix

[@jit3191]

I like the simple explanation.thanks

[@ByteByByte]

thanks :)

[@brinderdhaliwal3570]

Thanks for the clear solution. First time working through CTCI, and after working with c++, (all I've taken in my classes thus far) I was surprised that I could totally follow along with your Java solution and (mostly) understand it. CTCI kept mentioning Stringbuilder, but if I'm not mistaken, C++ doesn't use that so I was thrown off. Your approach seems much more simple, however I'm worried about the efficiency if asked this problem during an internship interview. What would be the BCR with this sort of solution?

[@ByteByByte]

As mentioned in the video (I think), not using a stringbuilder does affect the runtime. However, in my experience as long as you acknowledge that stringbuilders are a thing and you *could* use them, no interviewer will complain if you do it this way instead, since the code is much easier to follow

[@brinderdhaliwal3570]

Sounds good man, greatly appreciate the input.

[@itzeltravels]

How come we don't have to use the .equals method to compare the contents of s.chartAt(i) and s.charAt(i+ 1)? I thought that using == would return false since they are at different locations in the string. Thanks in advance!

[@ByteByByte]

In this case, we're comparing a primitive type, because charAt() returns a char as opposed to string

[@chaitanyakoranne]

Awesome series, but in this case, this program does not work for string - "aaabbcca" , expected output is - a4b2c2 and what we are getting is a3b2c2a1

[@AmitKumarGrrowingSlow]

char order should not be changed. If we hv to recreate the string you can't for a4b2c2...

[@MrAkshay2711]

Hey Sam always been fan of your videos. Learnt a lot of things. Just one doubt regarding this question, you mentioned that compressed string should be smaller than original string but case would not be possible when you have single character in string since it will always be greater than original string example "a" = "a1"; so I think return should only be compressed string and work without the check in the last? Correct me if I am wrong.

[@ByteByByte]

I'm simply saying that if the compressed string is longer, then don't compress the string. You're right that there are plenty of cases where the compressed string would be longer

[@sukrithisharrma3218]

please tell in string programs what is the meaning of int index=str[i]-'a'

[@ByteByByte]

well str[i] is a character and 'a' is a character. Both of those are represented as ASCII values, so index will be the index of the current character in the alphabet, assuming that str[i] is between 'a' and 'z'. For example 'a'-'a' = 0, 'b'-'a' = 1, 'z'-'a' = 25

[@arm8733]

How can we compress substrings instead of single characters in a String.For example Something like this :abababbbabba-> should output ab3bba2 ??

[@ByteByByte]

that would significantly complicate both the compressing and decompressing, but theoretically you could do it. The big question then becomes finding the optimally compressed string

[@Grassmpl]

for your 'char' issue, you could have just added the empty string first (out += ""+s.cahrAt(i)+sum)

[@ByteByByte]

certainly could although I feel like that makes the code harder to read

[@Rohitsingh2410]

will this work on "aaabbbaac"

[@ByteByByte]

you tell me

[@sung3898]

Shouldn't the last statement be out.length() "a2b2"

[@ByteByByte]

Could go either way. I opted to return the original string unless the compression actually shortened the string

[@mayankmicky5]

nice explanation but can u make a video on string uncompression plz :)

[@ByteByByte]

thanks! for string uncompression, you simply need to read the string character by character and whenever you see a number, duplicate the previous character that many times. I probably won't do a video about it, but I'm happy to help you with the code if you're stuck

[@mayankmicky5]

:) okay bro

I had to do this problem for an interview with Google. The compression part was fine but for decompression they asked me: How do you know if the string you receive is compressed? or if it's the original string? e.g originalString = "a2b2c2"; compressedString = "a2b2c2"; result = decompress(compressedString); result should be "a2b2c2" I said you could use some sort of extra variable to check this, like the length of the original string. I guess they didn't like the answer because I didn't get the job haha. Then I thought maybe using some sort of checksum of the original string? Anyway, hope to hear what you think.

[@ByteByByte]

Interesting. The way I usually think about the problem, you just assume that strings are only a-zA-Z, but obviously if you include numbers then it gets more complicated. Even more complicated if you consider two-digit numbers because how do you know whether its all one thing or not. Off the top of my head I can think of various things you could do to encode the numbers in specific ways. For example you could use an escape character like '\' if the number should be treated as a string instead of a count. You could also come up with some other way to encode the numbers. The main problem with the solutions that you're proposing are that they tell you if your decompression is wrong, but not how to fix it :)

[@zenospavlakou7991]

If you were to compress the string "abcde" using this algorithm the output would be "a1b1c1d1e1" which is twice as large. This is not compression. A good rule would be to add a number only when there are 3 or more repetitions because the string "aa" would compress to a2 which once again is not any smaller in size.

[@macmath22]

I think the sum should be incremented by one after while loop.

[@ramachandranv.p1432]

Wow u have been very observant with the explanation.Just striked me after u mentioned this!

[@chintalapativenkataramarahul]

Which loop are you talking about? I did not understand. Please could you be more specific.

[@udendranmudaliyar4458]

kindly make more video in Java ! God bless you ! amen

[@ByteByByte]

will do. thank you :)

[@jugsma6676]

The one I did is this way, Since my git is private I copy and paste my code right here: char firstChar = givenString.charAt(0); int count = 1; String compressedString = ""; for (int i=1; i < givenString.length(); i++) { if (firstChar == givenString.charAt(i)) count++; else { compressedString += firstChar + String.valueOf(count); count = 1; firstChar = givenString.charAt(i); } if (i == givenString.length() -1) { compressedString += firstChar + String.valueOf(count); } } return compressedString;

[@ByteByByte]

Looks reasonable

[@tanzeelrana7348]

public static String compress(String s) { String retString = ""; if (s.length() == 0) { return retString; } char current = s.charAt(0); int counter = 1; for (int i = 1; i < s.length(); i++) { if(s.charAt(i) != current) { retString += current; retString += counter; counter = 1; current = s.charAt(i); } else { counter++; } current = s.charAt(i); } retString += current; retString += counter; return retString; }

[@tanzeelrana7348]

for your solution using the following prints s String s = "gggffd"; System.out.println(compress(s)); output is "gggffd" but it should be "g3f2d1" so I wrote the above code.

[@aravindbros]

This doesnt work for the case "abb" The answer should be a1b2 but you print "abb" again since ( a1b2 - length 4 > abb - length 3).

[@ByteByByte]

that's the point. if the string doesn't actually get shorter, then you shouldn't compress it

[@louiswang538]

this is not in place

[@elisadevid5660]

Bestttt