Lesson

8.17Compress String

Problem Statement

Compress a string by shortening consecutive repeating characters to character+count.

Example Inputs

Input: "aabcccccaaa"
- Output: "a2b1c5a3"
Input: "abc"
- Output: "a1b1c1"
Input: "aaabb"
- Output: "a3b2"
Input: "aaAA"
- Output: "a2A2" (case-sensitive)

JavaScript Method - Using Only String Methods

Approach

To compress the string, we can iterate through each character while keeping track of consecutive repeating characters. When a character changes, we add the previous character and its count to the compressed string.

Steps

Initialize an empty string compressed and set count = 1.
Loop through each character in the string from the second character.
If the current character is the same as the previous, increment count.
If the character changes, append previous character + count to compressed and reset count to 1.
After the loop, add the final character and count to compressed.
Return the compressed string.

Time & Space Complexity

Time Complexity: O(n), where n is the length of the string, as each character is processed once.
Space Complexity: O(n), due to storing the compressed string.

Code Snippet

Pros and Cons

Pros

Concise and easy to read
Utilizes JavaScript string methods effectively for this problem
Handles edge cases like empty strings gracefully (using || [] fallback)

Cons

Depends on regex, which might be less intuitive for beginners
May not be as performant as manual loops for very large inputs, though generally negligible

This solution is clean and works well for the task of compressing strings with consecutive repeating characters.

Dry Run

Example input: "aabcccccaaa"

Initialize: compressed = "", count = 1
Loop through "aabcccccaaa":
- a === a → count = 2
- b !== a → compressed = "a2", count = 1
- c !== b → compressed = "a2b1", count = 1
- c === c → count = 2, continue counting c until count = 5
- a !== c → compressed = "a2b1c5", count = 1
Final append "a3" → compressed = "a2b1c5a3"
Final output: "a2b1c5a3"

Alternative Approach - Using Array Join

Approach

We can use an array to store compressed parts of the string and join them at the end for efficiency. This reduces concatenation overhead in each iteration.

Steps

Initialize an empty array compressedParts and set count = 1.
Loop through each character in the string starting from the second character.
If the current character is the same as the previous, increment count.
If the character changes, add previous character + count to compressedParts and reset count to 1.
After the loop, add the final character and count to compressedParts.
Return the joined array as a string.

Time & Space Complexity

Time Complexity: O(n), as each character is processed once.
Space Complexity: O(n), due to the array for compressed parts.

Code Snippet

Dry Run

Example input: "aabcccccaaa"

Initialize: compressedParts = [], count = 1
Loop through "aabcccccaaa":
- a === a → count = 2
- b !== a → compressedParts = ["a2"], count = 1
- c !== b → compressedParts = ["a2", "b1"], count = 1
- c === c → count = 2, continue counting c until count = 5
- a !== c → compressedParts = ["a2", "b1", "c5"], count = 1
Final append "a3" → compressedParts = ["a2", "b1", "c5", "a3"]
compressedParts.join('') → "a2b1c5a3"

Final output: "a2b1c5a3"

Complexity Analysis

JavaScript Method (Using String Methods)

Time Complexity: O(n)
Space Complexity: O(n)

Alternative Approach (Using Array Join)

Time Complexity: O(n)
Space Complexity: O(n)

Conclusion

String compression can be achieved by directly concatenating parts or by using an array and joining. Both approaches provide efficient solutions with linear time complexity.

Previous Next