How should I practice Shortest Compressed Length After Removal?

Start by reading the full statement, solve the visible examples, then compare the pattern against related DRW online assessment problems in FastPrep.

Is Shortest Compressed Length After Removal associated with DRW?

FastPrep tags this as a DRW coding interview or online assessment practice problem when the problem catalog has that company context.

Problem · String

Shortest Compressed Length After Removal

Learn this problem

● MediumDRWINTERNOA

Problem statement

A compressed representation replaces each maximal run of equal consecutive characters as follows:

A run of length 1 is represented by the character alone.
A run longer than 1 is represented by its decimal length followed by the character.

For example, ABBBCCCC compresses to A3B4C.

Given a string S of length N and an integer K, remove exactly K consecutive characters from S. Return the shortest possible length of the compressed representation of the remaining string.

The brackets in each HTML diagram mark the consecutive characters removed in that example.

┌───────────────┐     ┌───────┐
│ ABBBCC[DDC]CC │ ──▶ │ A3B4C │
└───────────────┘     └───────┘

┌──────────────────────────┐     ┌─────┐
│ AAAAAAAAAAA[BXX]AAAAAAAAAA │ ──▶ │ 21A │
└──────────────────────────┘     └─────┘

┌────────────┐     ┌───────┐
│ ABCDDD[EF]G │ ──▶ │ ABC3DG │
└────────────┘     └───────┘

Function

solution(S: String, K: int) → int

Examples

Example 1

S = "ABBBCCDDCCC"K = 3return = 5

Remove DDC to obtain ABBBCCCC. It compresses to A3B4C, whose length is 5.

Example 2

S = "AAAAAAAAAAABXXAAAAAAAAAA"K = 3return = 3

Remove BXX to leave twenty-one consecutive A characters. They compress to 21A, whose length is 3.

Example 3

S = "ABCDDDEFG"K = 2return = 6

Remove EF to obtain ABCDDDG. It compresses to ABC3DG, whose length is 6.