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