Leetcode 3163: String Compression III
You are given a string word. Compress the string using the following algorithm:
Begin with an empty string comp. While word is not empty, perform the following operation:
- Remove the longest prefix from
wordthat consists of the same character repeating up to 9 times. - Append the length of this prefix followed by the character to
comp. Return the resulting stringcomp.
Problem
Approach
Steps
Complexity
Input: The input consists of a string `word` that contains only lowercase English letters.
Example: Example 1:
Input: word = "xyz"
Output: "1x1y1z"
Constraints:
• 1 <= word.length <= 2 * 10^5
• word consists only of lowercase English letters.
Output: Return the string `comp` which is the compressed version of the input string `word`.
Example: Example 1:
Input: word = "xyz"
Output: "1x1y1z"
Constraints:
• The output will be a string.
Goal: The goal is to compress the string by iterating through it, identifying prefixes, and appending their length and character to the result.
Steps:
• Initialize an empty string `comp`.
• Iterate through the string `word`.
• For each group of consecutive identical characters (up to 9), append the length of the group followed by the character to `comp`.
• Return the resulting compressed string `comp`.
Goal: The input string must meet the following constraints.
Steps:
• 1 <= word.length <= 2 * 10^5
• word consists only of lowercase English letters.
Assumptions:
• The input string will not be empty.
• The input string contains only lowercase English letters.
• Input: Example 1:
• Explanation: For `word = "xyz"`, since there are no repeating characters, each character is treated as a separate group of length 1. Hence, the output is `"1x1y1z"`.
• Input: Example 2:
• Explanation: For `word = "aaaaaaaaaaaaaabb"`, we compress the string by grouping consecutive 'a's and 'b's. The first group has 9 'a's, the second has 5 'a's, and the last group has 2 'b's. Thus, the output is `"9a5a2b"`.
Approach: The approach is to iterate over the string, count the consecutive identical characters, and append the count and character to the result string. Continue this process until the entire string is compressed.
Observations:
• We need to ensure that we correctly handle sequences of repeated characters, especially those that repeat more than 9 times.
• By iterating over the string and counting consecutive characters, we can easily build the compressed string.
Steps:
• Initialize an empty result string `comp`.
• Use a while loop to traverse the string `word`.
• For each sequence of repeated characters (up to 9), count the number of characters and append the result to `comp`.
• Continue until the entire string has been processed.
• Return the final compressed string `comp`.
Empty Inputs:
• There will never be an empty string as input.
Large Inputs:
• The solution should handle strings with lengths up to 200,000 efficiently.
Special Values:
• Ensure the solution works with strings that have many repeated characters (e.g., 'aaaaaaaaaaaaaaaaaaaaaaaaaaa').
Constraints:
• Ensure that the solution works within time and space constraints for large inputs.
string compressedString(string word) {
int i = 0, n = word.size();
char cur;
string res = "";
while(i < n) {
int cnt = 0;
cur = word[i];
while(i < n && cnt < 9 && cur == word[i])
cnt++, i++;
res += to_string(cnt) + cur;
}
return res;
}
1 : Function Definition
string compressedString(string word) {
Defines the function 'compressedString' that accepts a string 'word' and returns its compressed form.
2 : Variable Initialization
int i = 0, n = word.size();
Initializes the index 'i' to 0 and 'n' to the length of the input string 'word'.
3 : Character Declaration
char cur;
Declares a variable 'cur' of type char to store the current character during the iteration.
4 : Result String Initialization
string res = "";
Initializes an empty string 'res' to store the result of the compressed string.
5 : Outer While Loop
while(i < n) {
Starts a while loop that runs as long as 'i' is less than the length of the string 'n'.
6 : Count Initialization
int cnt = 0;
Initializes a counter 'cnt' to 0 to keep track of consecutive occurrences of a character.
7 : Character Assignment
cur = word[i];
Assigns the current character at position 'i' in the string 'word' to the variable 'cur'.
8 : Inner While Loop
while(i < n && cnt < 9 && cur == word[i])
Starts a nested while loop that continues as long as the character at 'i' is the same as 'cur' and 'cnt' is less than 9.
9 : Counter Increment
cnt++, i++;
Increments the counter 'cnt' and the index 'i' as long as the current character matches 'cur'.
10 : Result String Update
res += to_string(cnt) + cur;
Appends the count 'cnt' (converted to a string) followed by the character 'cur' to the result string 'res'.
11 : Return Statement
return res;
Returns the compressed string 'res' as the output.
Best Case: O(n)
Average Case: O(n)
Worst Case: O(n)
Description: The time complexity is O(n), where `n` is the length of the string `word`. We traverse the string once, processing each character.
Best Case: O(n)
Worst Case: O(n)
Description: The space complexity is O(n) because we store the compressed string `comp` which could have a length up to the input string length in the worst case.
| LeetCode Solutions Library / DSA Sheets / Course Catalog |
|---|
comments powered by Disqus