Leetcode: String Compression

This question is asked at Goldman Sachs, Amazon, Microsoft, and Facebook.

Given an array of characters, compress in place. The length after compression must always be smaller than or equal to the original array. Every element in the array should be a character (not int) of length 1. After you are done modifying the input array in place, return the new length of the array. We also want to solve this using O(1) extra space.

Here's the first examples:

Input: 

["a", "a", "b", "b", "c", "c", "c"]

Output: Return 6, and the first 6 characters of the input array should be ["a", "2", "b", "c", "3"] because "aa" is replaced by "a2", "bb" is replaced by "b2" and "ccc" is replace by "c3".

Now example 2 if we are just given a single character ["a"] we return 1 since the first character of the input array should be ["a"] and that nothing is replaced. 

Here's the final examples:

["a", "b", "b", "b", "b", "b", "b", "b", "b", "b", "b", "b", "b"]

There's one occurrence of a and 12 occurrences of b, so it should be "a", "b12", which combines to "ab12", which makes the output as 4 characters. 

How would we compress the string? All we need to do is iterate through the whole string and for every single character, how many characters following that ith characters are the same. There would be i at the beginning of the string, and j indicating the number of occurrences for the character. The string will occur a total of j - i times.  We keep going through that process, j will then point to c and i will move to the beginning of the string and we reach the end of the array, and we put into the array how many times you saw a specific string. 

For the second case, if we were given "a" we would just have "a" and we'd actually return 1 because we have i and j pointing to a then we move j and would be end of the array would be j - i = 1 but the answer is 1. We output 1 is the length, so we only want to place the occurrence whenever j - i is strictly greater than 1. 

For the third string, we have i = a and j = a  and when we move j forward it's not the same, so j - i = 1 and not greater than 1 so we don't want to compress that, so far we just have the letter a.

Then we see b so i = 1 j = 1, and the j keeps moving to the end of the array, and j - i = 12 since i = 1 and j = 13. 

Here's the code: 

class Solution {

    public int compress(char[] chars) {

        int index = 0;

        int i = 0;

        while(i < chars.length) {

            //start j

            int j = i;

            //increment j until you reach a different character

            while(j < chars.length && chars[j] == chars[i]) {

                j++;

             }

            //the index is now the new i character

            chars[index] = chars[i];

            index++;

            //if there is more than one occurrence of the character

            if(j - 1 > 1) {

                String count = j - i + "";

                //in place, put the count into an array in the pointer

                for(char c: count.toCharArray()) {

                    chars[index] = c;

                    index++;

                }

            }

            //move the i index to the beginning of the next character

           i = j; 

         }

        return index;

    }

}

Now it's time to code in Java. Here it is with commentary: 

class Solution {

    public int compress(char[] chars) {

        //traverse through index for both the array and the new array we create in-place 

        int indexAns = 0;

        int index = 0;

        while(index < chars.length) {

            //the current character

            char currentChar = chars[index];

            int count = 0;

            while(index < chars.length && chars[index] == currentChar) {

                //increment until there is a different number

                index++;

                count++;

            }

            //get the first character

            chars[indexAns++] = currentChar;

            if(count != 1) {

                //put the occurrences for the character

                for(char c : Integer.toString(count.toCharArray());

                chars[indexAns++] = c;

            }

            //return the index of the last character aka "new" array from 0 to indexAns

            return indexAns;

        }

    }

}