String Compression III

Susan Sarandon
Release: 2024-11-05 07:08:02
Original
419 people have browsed it

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






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:

  • LinkedIn
  • GitHub

The above is the detailed content of String Compression III. For more information, please follow other related articles on the PHP Chinese website!

source:dev.to
Statement of this Website
The content of this article is voluntarily contributed by netizens, and the copyright belongs to the original author. This site does not assume corresponding legal responsibility. If you find any content suspected of plagiarism or infringement, please contact admin@php.cn
Latest Articles by Author
Popular Tutorials
More>
Latest Downloads
More>
Web Effects
Website Source Code
Website Materials
Front End Template