Skip to content

Instantly share code, notes, and snippets.

@ritik-agrawal
Created August 6, 2023 07:53
Show Gist options
  • Save ritik-agrawal/898cafedb7f477e3cc230102484a6ec0 to your computer and use it in GitHub Desktop.
Save ritik-agrawal/898cafedb7f477e3cc230102484a6ec0 to your computer and use it in GitHub Desktop.
LeetCode: Compress string question
class Solution {
public int compress(char[] chars) {
var len = chars.length;
var count = 1;
if (len == 1){
return count;
}
var mark = 0;
var charCnt = 1;
for (int i = 1; i < len; i++){
if (chars[i-1] == chars[i]){
charCnt++;
} else {
mark = write(chars, charCnt, mark, i);
charCnt = 1;
}
}
if (charCnt == 1){
chars[mark++] = chars[len -1];
} else {
mark = write(chars, charCnt, mark, (len -1));
}
return mark;
}
private int write(char[] chars, int charCnt, int mark, int i){
chars[mark++] = chars[i-1];
if (charCnt > 1){
var str = String.valueOf(charCnt);
var slen = str.length();
var j = 0;
while (j < slen){
chars[mark++] = str.charAt(j++);
}
}
return mark;
}
}
@ritik-agrawal
Copy link
Author

Question

Given an array of characters chars, compress it using the following algorithm:

Begin with an empty string s. For each group of consecutive repeating characters in chars:

  • If the group's length is 1, append the character to s.
  • Otherwise, append the character followed by the group's length.
    The compressed string s should not be returned separately, but instead, be stored in the input character array chars. Note that group lengths that are 10 or longer will be split into multiple characters in chars.

After you are done modifying the input array, return the new length of the array.

You must write an algorithm that uses only constant extra space.

@ritik-agrawal
Copy link
Author

Achievement

The above code is implemented by me which beats 97% of the total solutions submitted in terms of runtime as per the Leet code console.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment