 # 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 Design HashSet solution using TypeScript Fizz Buzz solution using TypeScript Pascal's Triangle solution using TypeScript Min Stack solution using TypeScript Symmetric Tree solution using TypeScript Same Tree solution using TypeScript