We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

String Compression

Number: 443

Difficulty: Medium

Paid? No

Companies: Yandex, Amazon, Salesforce, Meta, Goldman Sachs, Google, Microsoft, ServiceNow, Apple, Oracle, Bloomberg, CrowdStrike, Affirm, IBM, TikTok, Palo Alto Networks, Ripple, Pinterest, Adobe, Uber, PhonePe, Expedia, GoDaddy, Snap, Yelp, Lyft

Problem Description

Given an array of characters, compress it in-place using a simple algorithm. For every group of consecutive repeating characters, append the character followed by the number of times it appears if the count is more than 1. The final compressed string must be stored in the same input array and the algorithm should use constant extra space.

Key Insights

  • Use a two-pointer approach: one pointer for reading the original characters and one for writing the compressed result.
  • Iterate through the array, counting consecutive duplicates.
  • Write the character to the result followed by its count (if greater than 1), converting the count to its string representation.
  • The algorithm works in-place with constant extra space aside from the counter and temporary variables.

Space and Time Complexity

Time Complexity: O(n), where n is the number of characters in the array. Space Complexity: O(1) (in-place compression with only a few extra variables).

Solution

The solution leverages a two-pointer technique:

  • A "read" pointer traverses the array to identify groups of repeated characters.
  • A "write" pointer updates the array with the compressed characters.
  • For each group, after writing the character, if the group size is more than 1, the count is converted to a string and each digit is written sequentially.
  • This in-place modification ensures constant extra space and the entire array is scanned once, resulting in O(n) time complexity.

Code Solutions

# Function to compress the list of characters in-place.
def compress(chars):
    # Initialize read and write pointers.
    read, write = 0, 0
    # Loop until the read pointer reaches the end of the array.
    while read < len(chars):
        # Current character to be processed.
        current_char = chars[read]
        count = 0
        # Count duplicates of current_char.
        while read < len(chars) and chars[read] == current_char:
            read += 1
            count += 1
        # Write the current character to the result.
        chars[write] = current_char
        write += 1
        # If count is greater than 1, write each digit of the count.
        if count > 1:
            for digit in str(count):
                chars[write] = digit
                write += 1
    # Return the new length of the array.
    return write

# Example usage:
# chars = ["a","a","b","b","c","c","c"]
# new_length = compress(chars)
# print(new_length, chars[:new_length])
← Back to All Questions