DEV Community

Cover image for 3163. String Compression III
MD ARIFUL HAQUE
MD ARIFUL HAQUE

Posted on

3163. String Compression III

3163. String Compression III

Difficulty: Medium

Topics: String

Given a string word, compress it using the following algorithm:

  • Begin with an empty string comp. While word is not empty, use the following operation:
    • Remove a maximum length prefix of word made of a single character c repeating at most 9 times.
    • Append the length of the prefix followed by c to comp.

Return the string comp.

Example 1:

  • Input: word = "abcde"
  • Output: "1a1b1c1d1e"
  • Explanation: Initially, comp = "". Apply the operation 5 times, choosing "a", "b", "c", "d", and "e" as the prefix in each operation.
    • For each prefix, append "1" followed by the character to comp.

Example 2:

  • Input: word = "aaaaaaaaaaaaaabb"
  • Output: "9a5a2b"
  • Explanation: Initially, comp = "". Apply the operation 3 times, choosing "aaaaaaaaa", "aaaaa", and "bb" as the prefix in each operation.
    • For prefix "aaaaaaaaa", append "9" followed by "a" to comp.
    • For prefix "aaaaa", append "5" followed by "a" to comp.
    • For prefix "bb", append "2" followed by "b" to comp.

Constraints:

  • 1 <= word.length <= 2 * 105
  • word consists only of lowercase English letters.

Hint:

  1. Each time, just cut the same character in prefix up to at max 9 times. It’s always better to cut a bigger prefix.

Solution:

We can use a greedy approach to compress the string by taking the longest possible prefix of repeating characters (up to 9 occurrences at a time) and then appending the length of the prefix along with the character to the result.

Here's the step-by-step solution:

  1. Initialize Variables:

    • comp (the compressed string) starts as an empty string.
    • Use a pointer or index i to track the position in the word.
  2. Loop through word:

    • While there are characters left in word, find the longest prefix of repeating characters that does not exceed 9 characters.
    • Count how many times the current character repeats consecutively, up to a maximum of 9.
  3. Append to Compressed String:

    • Append the count followed by the character to comp.
    • Move the pointer i forward by the number of characters processed.
  4. Return Result:

    • After processing the entire string, return the compressed string comp.

Let's implement this solution in PHP: 3163. String Compression III

<?php
/**
 * @param String $word
 * @return String
 */
function compressString($word) {
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

// Test cases
echo compressString("abcde");          // Output: "1a1b1c1d1e"
echo "\n";
echo compressString("aaaaaaaaaaaaaabb"); // Output: "9a5a2b"
?>
Enter fullscreen mode Exit fullscreen mode

Explanation:

  • Counting Loop: We use a while loop inside the main loop to count consecutive characters (up to 9) for each unique character in word.
  • Appending Results: After counting each sequence, we append the count and character directly to comp.
  • Pointer Update: The main loop pointer i moves forward by the number of characters counted, effectively reducing the size of the remaining string in each iteration.

Complexity Analysis

  • Time Complexity: O(n), where n is the length of word. Each character is processed once.
  • Space Complexity: O(n) for the compressed result stored in comp.

This solution is efficient and handles edge cases, such as sequences shorter than 9 characters or a single occurrence of each character.

Contact Links

If you found this series helpful, please consider giving the repository a star on GitHub or sharing the post on your favorite social networks 😍. Your support would mean a lot to me!

If you want more helpful content like this, feel free to follow me:

Image of Timescale

Timescale – the developer's data platform for modern apps, built on PostgreSQL

Timescale Cloud is PostgreSQL optimized for speed, scale, and performance. Over 3 million IoT, AI, crypto, and dev tool apps are powered by Timescale. Try it free today! No credit card required.

Try free

Top comments (0)

AWS Security LIVE!

Tune in for AWS Security LIVE!

Join AWS Security LIVE! for expert insights and actionable tips to protect your organization and keep security teams prepared.

Learn More

👋 Kindness is contagious

Discover a treasure trove of wisdom within this insightful piece, highly respected in the nurturing DEV Community enviroment. Developers, whether novice or expert, are encouraged to participate and add to our shared knowledge basin.

A simple "thank you" can illuminate someone's day. Express your appreciation in the comments section!

On DEV, sharing ideas smoothens our journey and strengthens our community ties. Learn something useful? Offering a quick thanks to the author is deeply appreciated.

Okay