leetcode

String Compression solution using TypeScript

This post outlines my TypeScript solution to the "String Compression" question on LeetCode using an iterative approach.

Algorithm: The solution uses two pointers to iterate over the inputted array.

  • Check the character at the left pointer
  • Move the right pointer to the right until it points to a non-repeating character.
  • The set of characters between the left and right pointer now represent a set of repeating characters.
  • Replace the set of repeating characters with their compressed representation.
  • Move the pointers to the last element of the compressed set.
  • Repeat the above steps until all sets of repeating characters have been compressed.

Time Complexity: Because the array will be traversed only one time, the time complexity is O(n) where n represents the number of elements in the array.

Space Complexity: Because the solution will use a constant amount of space, the space complexity is O(1).

/**
 * String Compression
 * 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.
 *
 * Time Complexity: O(n)
 * Space Complexity: O(1)
 *
 * compress(["a","a","b","b","c","c","c"])
 *    // 6, ["a","2","b","2","c","3"]
 * compress(["a","b","b","b","b","b","b","b","b","b","b","b"])
 *    // 3, ["a","b","1","1"]
 */
function compress(chars: string[]): number {
    // create two pointers
    let left = 0;
    let right = 0;

    /*
     * Take the char at the left pointer and move the 
     * right pointer until a non-repeating char is encountered.
     * Take that set of repeated characters and replace them
     * with their compressed representation. The pointers are
     * then set to the last element of the compressed set.
     */
    while (right < chars.length) {
        let char = chars[left];

        // move right pointer until a non-repeating char is found
        while (chars[right] === char) {
            right += 1;
        }

        // compress the set of repeating characters
        const repeated = right - left;
        const compressed = repeated > 1
            ? [char, ...repeated.toString().split('')]
            : [char];
        chars.splice(left, repeated, ...compressed);

        // update the pointers and account for resized array
        left = left + compressed.length;
        right = left;
    }
    
    return chars.length;
}

more LeetCode posts