Compress Consecutive Character Groups In Place

Quick Overview

Practice compressing consecutive character groups into the original array with constant extra space. Preserve multi-digit count order, mutation semantics, and ordinary digit or symbol characters.

Compress Consecutive Character Groups In Place

Company: Google

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Other

# Compress Consecutive Character Groups In Place Compress the character array `chars` by processing its maximal consecutive groups: - A group of length one contributes only its character. - A longer group contributes its character followed by the group's decimal length, with each digit stored as a separate character. Write the result into the beginning of `chars` itself and return its length. Do not return a separate compressed string. Characters beyond the returned length are ignored. Use only constant extra space. ### Function `int compress(vector<char>& chars)` ### Example 1 ```text Input: chars = ["x","x","x","x","x","x","x","x","x","x","x","x","."] Output length: 4 Required prefix: ["x","1","2","."] ``` ### Example 2 ```text Input: chars = ["1","1","!","!","!","A"] Output length: 5 Required prefix: ["1","2","!","3","A"] ``` ### Constraints - `1 <= chars.length <= 2000`. - Each entry is a lowercase letter, uppercase letter, digit, or symbol. ### Clarifications Only consecutive equal characters belong to one group. Count one is omitted. Original digit characters are ordinary group characters; they are not preexisting counts to parse. The returned length and the mutated prefix are both required, while the remaining array contents do not matter. ### What a Strong Answer Covers - Identifying complete groups and emitting multi-digit counts in the correct order. - Singletons, adjacent groups, digits, and symbols. - Why writing the prefix does not destroy unread input. - Correctness, mutation semantics, and the constant-space bound.

Overview: Practice compressing consecutive character groups into the original array with constant extra space. Preserve multi-digit count order, mutation semantics, and ordinary digit or symbol characters.

Google logo
Google
mediumSoftware EngineerOtherCoding & Algorithms
0
0

Compress Consecutive Character Groups In Place

Compress the character array chars by processing its maximal consecutive groups:

  • A group of length one contributes only its character.
  • A longer group contributes its character followed by the group's decimal length, with each digit stored as a separate character.

Write the result into the beginning of chars itself and return its length. Do not return a separate compressed string. Characters beyond the returned length are ignored.

Use only constant extra space.

Function

int compress(vector<char>& chars)

Example 1

Input: chars = ["x","x","x","x","x","x","x","x","x","x","x","x","."]
Output length: 4
Required prefix: ["x","1","2","."]

Example 2

Input: chars = ["1","1","!","!","!","A"]
Output length: 5
Required prefix: ["1","2","!","3","A"]

Constraints

  • 1 <= chars.length <= 2000 .
  • Each entry is a lowercase letter, uppercase letter, digit, or symbol.

Clarifications

Only consecutive equal characters belong to one group. Count one is omitted. Original digit characters are ordinary group characters; they are not preexisting counts to parse. The returned length and the mutated prefix are both required, while the remaining array contents do not matter.

What a Strong Answer Covers Guidance

  • Identifying complete groups and emitting multi-digit counts in the correct order.
  • Singletons, adjacent groups, digits, and symbols.
  • Why writing the prefix does not destroy unread input.
  • Correctness, mutation semantics, and the constant-space bound.