Created
August 6, 2023 07:53
-
-
Save ritik-agrawal/898cafedb7f477e3cc230102484a6ec0 to your computer and use it in GitHub Desktop.
LeetCode: Compress string question
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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; | |
} | |
} |
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
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:s
.The compressed string
s
should not be returned separately, but instead, be stored in the input character arraychars
. Note that group lengths that are 10 or longer will be split into multiple characters inchars
.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.