Solution.java

package stringcompression;

/**
 * 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 int) of length 1.
 *
 * After you are done modifying the input array in-place, return the new length of the array.
 *
 *
 * Follow up:
 * Could you solve it using only O(1) extra space?
 *
 *
 * Example 1:
 *
 * 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","2","c","3"]
 *
 * Explanation:
 * "aa" is replaced by "a2". "bb" is replaced by "b2". "ccc" is replaced by "c3".
 *
 *
 * Example 2:
 *
 * Input:
 * ["a"]
 *
 * Output:
 * Return 1, and the first 1 characters of the input array should be: ["a"]
 *
 * Explanation:
 * Nothing is replaced.
 *
 *
 * Example 3:
 *
 * Input:
 * ["a","b","b","b","b","b","b","b","b","b","b","b","b"]
 *
 * Output:
 * Return 4, and the first 4 characters of the input array should be: ["a","b","1","2"].
 *
 * Explanation:
 * Since the character "a" does not repeat, it is not compressed. "bbbbbbbbbbbb" is replaced by "b12".
 * Notice each digit has it's own entry in the array.
 *
 *
 * Note:
 *
 * All characters have an ASCII value in [35, 126].
 * 1 <= len(chars) <= 1000.
 */

 class Solution {
    
    /**
     * Time: O(N), N is length of chars
     * Space: O(1), no extra space is used
     *
     * Runtime: 1 ms, faster than 92.75% of Java online submissions for String Compression.
     * Memory Usage: 38.8 MB, less than 6.82% of Java online submissions for String Compression.
     *
     */
     int compress(char[] chars) {
        if(chars.length == 1) return 1;
        int i = 0, j = i+1, count = 1, writePos = 0;
        String countStr = "";
        while(writePos < chars.length) {
            while(j < chars.length && chars[i] == chars[j]) {
                j++; count++;
            }
            // write count only if > 1
            chars[writePos++] = chars[i];
            if(count > 1) {
                countStr = String.valueOf(count);
                for(char c: countStr.toCharArray()) {
                    chars[writePos++] = c;
                }
            }

            if(j >= chars.length)
                break;
            i = j;
            j = i+1;
            count = 1;
        }
        return writePos;
    }

}