🟨 JavaScript
Medium
🕐 15 min

String Compression (Run-Length Encoding)

Goal: Implement a string compression algorithm that efficiently groups sequences of identical characters.

💡 Hint

There are two popular approaches to solving this problem:

  1. Iterative Approach (for loop):

    • Iterate through the string, keeping track of the current character and its count.
    • If the next character is different from the current one (or the string has ended), append the current character and its count (if it’s greater than 1) to the result.
    • Reset the counter and continue.
  2. Using Regular Expressions:

    • You can use a regular expression to find all sequences of identical characters.
    • The expression /(.)\1*/g is perfect for this: (.) captures any character, and \1* looks for its repetitions.
    • Use the replace method with a callback function to format the result.
👀 Solution #1 (for loop)
const compressString = (str) => {
  // If the string is empty, there's no point in continuing. Return an empty string.
  if (!str) {
    return '';
  }
 
  // `result` will store our compressed string.
  let result = '';
  // `count` tracks the number of repetitions for the current character.
  let count = 1;
 
  // Iterate through the string using a for loop.
  for (let i = 0; i < str.length; i++) {
    // Look ahead: compare the current character (str[i]) with the next one (str[i + 1]).
    // If they match, the sequence continues.
    if (str[i] === str[i + 1]) {
      // Just increment the counter and move to the next iteration.
      count++;
    } else {
      // If the next character is different or it's the end of the string,
      // it means the sequence of the current character has been interrupted.
 
      // Append the character itself to the result.
      // Then check the counter: if it's greater than 1, append it as well.
      // If the counter is 1, we add nothing, as per the requirements.
      result += str[i] + (count > 1 ? count : '');
      
      // Reset the counter to 1 for the next sequence of characters.
      count = 1;
    }
  }
 
  // Return the final compressed string.
  return result;
};

Solution Analysis:

  • Pros:

    • Clarity: The code is easy to read and understand because the logic is implemented step-by-step.
    • Performance: This is usually the fastest approach as it avoids the overhead of creating and compiling regular expressions.
    • Control: Full control over the iteration and processing logic.
  • Cons:

    • Verbosity: Requires more code compared to the regular expression solution.
    • State Management: You need to manually manage the result and count variables.
👀 Solution #2 (Regular Expressions)
const compressString = (str) => {
  // Simple check for an empty string.
  if (!str) {
    return '';
  }
 
  // Use the `replace` method with a regular expression.
  // The regular expression /(.)\1*/g finds all sequences
  // of identical characters in the string.
  // ( . ) - Captures any single character (except newline) into a group.
  // \1*   - Matches zero or more repetitions of what was captured in the first group.
  // g     - Global flag to find all matches, not just the first one.
  return str.replace(/(.)\1*/g, (match, char) => {
    // `replace` calls this callback function for each match found.
    // `match` is the entire matched sequence (e.g., "AAAA").
    // `char` is the character captured by the first group (e.g., "A").
 
    // If the length of the matched sequence is greater than 1,
    // return the character + its length.
    // Otherwise (if the length is 1), return only the character itself.
    return match.length > 1 ? char + match.length : char;
  });
};

Solution Analysis:

  • Pros:

    • Conciseness: The solution is very concise and elegant.
    • Declarative: You describe what to find (a pattern), not how to do it (iteration).
  • Cons:

    • Readability: Can be difficult to understand if you are not familiar with regular expressions.
    • Performance: On very large strings, it might be slower than a loop due to the complexity of the regex engine. However, for most cases, the difference will be negligible.

Task Description

You need to create a function compressString that performs basic string compression using the Run-Length Encoding (RLE) algorithm.

Compression Rules:

  1. If a sequence consists of a single character, it remains unchanged.
  2. If a character is repeated in a sequence, it is replaced by the character itself, followed by the number of repetitions.

Examples

// 'AAA' -> 'A3', 'B' -> 'B', 'CC' -> 'C2'
compressString('AAABCC'); // "A3BC2"
 
// No consecutive repetitions
compressString('ABC'); // "ABC"
 
// Long sequence
compressString('WWWWWWWWWWWW'); // "W12"
 
// Empty string
compressString(''); // ""

Requirements

  • The function must be named compressString.
  • The function must handle empty strings correctly.
  • The function must be case-sensitive ('a' and 'A' are different characters).

🧑‍💻 It's not a bug! It's a feature!

The code editor is intentionally hidden on mobile.

Believe me, it's for the best: I am protecting you from the temptation to code in less-than-ideal conditions. A small screen and a virtual keyboard are not the best tools for a programmer.

📖 Now: Study the task, think through the solution. Act like a strategist.

💻 Later: Sit down at your computer, open the site, and implement all your ideas comfortably. Act like a code-jedi!