How do you solve String Compression on LeetCode?

String Compression (LeetCode #443) can be solved using Brute Force or Optimal Solution. The optimal approach is Optimal Solution with O(n) time complexity and O(1) space complexity. Key insight: Using two pointers allows in-place modification, which is efficient.

What is the brute force solution for String Compression?

The brute force approach for String Compression is Brute Force, with O(n²) time complexity and O(1) space complexity. The brute-force approach involves iterating through the array and building a new string based on the counts of consecutive characters. This method is straightforward but inefficient due to repeated string concatenation. The optimal Optimal Solution approach improves this to O(n).

What algorithm or data structure is used to solve String Compression?

String Compression uses the following concepts: Two Pointers, String. The recommended patterns to study are: Two Pointers, String Manipulation.

What are the interview tips for String Compression?

Always clarify the problem constraints, especially regarding space usage. Think about edge cases, such as single characters or long sequences. Practice in-place algorithms to get comfortable with pointer manipulation.

What are common mistakes when solving String Compression?

Not handling counts greater than 9 correctly. Confusing the read and write pointers, leading to incorrect array modifications.

#443

String Compression

Medium

Two PointersStringTwo PointersString Manipulation

LeetCode ↗

Approaches

Brute ForceOptimal

Complexity Comparison

	Brute Force	Optimal Solution★
Time	O(n²)	O(n)
Space	O(1)	O(1)

💡

Intuition

Time O(n)Space O(1)

The optimal solution uses a two-pointer technique to compress the string in-place without needing extra space for a new string. This approach is efficient and adheres to the problem's constraints.

⚙️

Algorithm

5 steps

1Step 1: Initialize two pointers: one for reading the characters and another for writing the compressed result.
2Step 2: Use the read pointer to traverse the array and count consecutive characters.
3Step 3: When a different character is found, write the character and its count (if greater than 1) to the write pointer.
4Step 4: Move the write pointer accordingly and repeat until the end of the array.
5Step 5: Return the write pointer as the new length of the array.

solution.py21 lines

1# Full working Python code
2chars = ['a', 'a', 'b', 'b', 'c', 'c', 'c']
3
4def compress(chars):
5    write = 0
6    read = 0
7    while read < len(chars):
8        char = chars[read]
9        count = 0
10        while read < len(chars) and chars[read] == char:
11            read += 1
12            count += 1
13        chars[write] = char
14        write += 1
15        if count > 1:
16            for digit in str(count):
17                chars[write] = digit
18                write += 1
19    return write
20
21print(compress(chars))

ℹ

Complexity note: The time complexity is O(n) because we only traverse the array once. The space complexity is O(1) since we are modifying the input array in place and not using any additional data structures that grow with input size.

1Using two pointers allows in-place modification, which is efficient.
2Counting consecutive characters helps in compressing the string effectively.

Solutions and explanations are original Tejav content. Problem titles © LeetCode — use the LeetCode button above for the full problem statement.