Interview Question: String Compression

In this video, I show how compress repeated characters in a string.

Do you have a big interview coming up with Google or Facebook? Do you want to ace your coding interviews once and for all? If so, Byte by Byte has everything that you need to go to get your dream job. We've helped thousands of students improve their interviewing and we can help you too.

You can also find me on

[martincopes]

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.

[josiegeng]

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

[fxsabreu]

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

[fredianriko]

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

[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.

[brinderdhaliwal]

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?

[MrAkshay]

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.

[Grassmpl]

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

[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

[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!

[mayankmicky]

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

[jugsma]

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;

[udendranmudaliyar]

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

[sukrithisharrma]

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

[arm]

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

[zenospavlakou]

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.

[tanzeelrana]

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;
}

[sung]

Shouldn't the last statement be out.length() <= s.length() ? out : s
e.g. "aabb" -> "a2b2"

[macmath]

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